上一篇文章中,我们实现了Scheme中的变量和环境。有了这些基础设施,现在可以将原生的字符串解析为S表达式。Scheme的文法比较简单,使用手写的LL(1)文法解析器也是可行的,但是为了日后维护和修改上的方便,还是使用词法分析和句法分析工具更佳。本项目中,词法分析工具为Flex,句法分析工具为Bison。

词法分析

词法分析程序对应源代码中的lexer.lex,对于不同的token,处理方式如下:

  • 对于字符串、符号、数值:将值放入yylval变量中,同时对应返回token类型;

  • 对于(、)、’、,、EOF这些构成S表达式结构的字符:返回对应的token类型;

  • 对于空格和注释:将所有连续的空格和注释读入,返回一个表示空格分割的token类型。

%top {
#include <string>
#include "variable.hpp"
#include "parser.hpp"
}

%option noyywrap
%option c++

line_comment		\;[^\r\n]*(\r|\n)
block_comment		\#\|([^\|]|\|[^\#])*\|\#
comment 		{line_comment}|{block_comment}
divider 		(\r|\n|\t|" "|{comment})+
digit			[[:digit:]]
signed			-?
rational		{signed}{digit}+(\/{digit}+)?
double			{signed}{digit}+(\.{digit}+)?((e|E){signed}{digit}+)?
symbol			[^'\"\(\)\.\r\n" "]+
string 			\"(\\\"|[^\"])*\"

%%

<<EOF>>			return END_OF_FILE;
\(			return LEFT_PARENTHESES;
\)			return RIGHT_PARENTHESES;
'			return QUOTE;
\.			return DOT;
{string}		{ 
	yylval = Variable(std::string(YYText()+1, YYText()+YYLeng()-1), Variable::TYPE_STRING); 
	return STRING; 
}
{rational}		{
	yylval = Variable(YYText(), Variable::TYPE_RATIONAL);
	return RATIONAL;
}
{double}		{
	yylval = Variable(YYText(), Variable::TYPE_DOUBLE);
	return DOUBLE;
}
{symbol}		{
	yylval = Variable(YYText(), Variable::TYPE_SYMBOL);
	return SYMBOL;
}
{divider}		return DIVIDER;

%%

语法分析

句法分析程序对应源代码中的parser.yacc,需要注意以下问题:

  • S表达式中的空格:虽然从人类的角度来看,S表达式的语法非常简单,但是空格在S表达式中的作用非常灵活,因此需要在语法中处理好空格的作用;

  • 标准I/O流的支持:在不做任何设定的前提下,分析器从标准输入流读取字符。但是,作为解析器,应该具备从任何输入流读取字符的能力,需要增加一个函数接口来实现从某个输入流读取字符进行语法分析。

%code top {
#include <iostream>
#include <FlexLexer.h>
#include "variable.hpp"
#include "parser.hpp"

yyFlexLexer lexer;		
Variable yypval = VAR_NULL;

int yylex();				
void yyerror(char const *);
}

%define api.value.type {Variable}

%token LEFT_PARENTHESES
%token RIGHT_PARENTHESES
%token QUOTE
%token DOT
%token STRING
%token RATIONAL
%token DOUBLE
%token SYMBOL
%token DIVIDER
%token END_OF_FILE

%%

input:
  %empty		{ return EOF;	}
| END_OF_FILE 		{ return EOF;	}
| DIVIDER END_OF_FILE 	{ return EOF;	}
| exp					{ yypval = $1; return 0;	}
| DIVIDER exp		{ yypval = $2; return 0;	}
;

exp:
  RATIONAL 											{ $$ = $1;	}
| DOUBLE 											{ $$ = $1;	}
| SYMBOL 											{ $$ = $1;	}
| STRING 											{ $$ = $1;	}
| LEFT_PARENTHESES seq RIGHT_PARENTHESES			{ $$ = $2;	}
| LEFT_PARENTHESES DIVIDER seq RIGHT_PARENTHESES	{ $$ = $3;	}
| QUOTE exp											{ 
	$$ = Variable(Variable("quote", Variable::TYPE_SYMBOL),Variable($2,VAR_NULL));	
}
| QUOTE DIVIDER exp									{ 
	$$ = Variable(Variable("quote", Variable::TYPE_SYMBOL),Variable($3,VAR_NULL));	
}
;

seq:
  %empty						{ $$ = VAR_NULL;				}
| exp seq						{ $$ = Variable($1,$2);			}
| exp DIVIDER seq				{ $$ = Variable($1,$3);			}
| exp DIVIDER DOT DIVIDER exp	{ $$ = Variable($1,$5);			}

%%

void yyerror(char const *s)
{
	std::cerr << s << std::endl;
}

int yylex()
{ 
	return lexer.yylex();
}

int yyparse(std::istream* in, std::ostream* out = 0)
{
	lexer.switch_streams(in, out);
	return yyparse();
}

解析器接口

在完成解析器之后,将Variable(variable.cpp)类型的标准输入作为解析器接口,解析器从输入流读取字符,将解析获得的值存入var中。

extern int yyparse(std::istream* in, std::ostream* out = 0);
extern Variable yypval;

istream& operator>>(istream& in, Variable& var)
{
	yyparse(&in);
	var = yypval;
	return in;
}