toy LL(k) parser
Mini语言是C语言的子集,其支持的部分C语言语法规则及示例如下:
- 源代码为空(以#结尾)或由语句、语句块、控制结构(if/while)组成
- 语句必须以;结尾
- 语句块必须用{}包裹,仅含一条语句的除外
- 变量声明语句
- 如:int a;
- 支持的变量类型有:{int, float, double, bool}
- 支持声明时赋值
- int a = 0;
- 赋值语句
- 如:a = 0;
- 支持右结合的连续赋值,如:a = b = c;
- If分支结构
- 如:if (a == 0) { a = 1; } else { a = 2; }
- While循环结构
- 如:while (a == 0) { a = a + 1; }
- 运算表达式
- 除优先级运算符小括号外仅支持二元运算符:{'+', '-', '*', '/', '%', '=','(', ')', '>', '<', '^', '!', '&', '|', '%', '==', '!=', '>=', '<=', '&&', '||'}
- 结合性:右结合。由于MiniParser采用递归下降分析法实现,适用于LL(k)文法,故无法包含左递归,只有右递归。右递归对应右结合
- 不支持左结合的连续运算,如:a - a - a、a || a || a、a > a > a
- 优先级:小括号 > 乘除 > 加减 > 比较 > 判等(如==) > 位与 > 位异或 > 位或 > 逻辑与 > 逻辑或
为实现方便,减少产生式(子程序)数量,Mini语言文法G[<源程序>]为LL(3)型文法,但绝大多数产生式在读取1个token即可被确定。文法定义包括开始符号、终结符、非终结符、产生式:
- 开始符号:<源程序>
- 终结符、非终结符:鉴于符号众多,不另行写出集合,而是约定在产生式中由‘’包裹的为终结符,由<>包裹的为非终结符
- 产生式(分为三类,分别用不同字体表示):
<源程序> → <语句><源程序> | epsilon
<语句块> → <语句> | ‘{’<源程序>‘}’
<语句> → <声明语句> | <赋值语句> | <IF结构> | <WHILE结构>
<声明语句> → <变量类型> <标识符>‘;’| <变量类型> <赋值语句>
<赋值语句> → <赋值>‘;’
<赋值> → <标识符>‘=’(<标识符> | <表达式> | <赋值>)
<IF结构> → ‘if’‘(’<表达式>‘)’(<语句块> | <语句块>‘else’<语句块>)
<WHILE结构> → ‘while’‘(’<表达式>‘)’<语句块>
<表达式> → <逻辑与式> ‘||’<逻辑与式>
<逻辑与式> → <位或式> ‘&&’<位或式>
<位或式> → <位异或式> ‘|’<位异或式>
<位异或式> → <位与式> ‘^’<位与式>
<位与式> → <判等式> ‘&’<判等式>
<判等式> → <比较式> (‘==’|‘!=’)<比较式>
<比较式> → <加减式> (‘>’|‘<’|‘>=’|‘<=’)<加减式>
<加减式> → <乘除式>(‘+’|‘-’)<乘除式>
<乘除式> → <括号式> (‘*’| ‘/’ | ‘%’)<括号式>
<括号式> → ‘(’<表达式>‘)’| <标识符> | <常量>
<变量类型> → ‘int’| ‘float’| ‘double’| ‘bool’
<标识符> → ‘标识符表中的变量名称’
<常量> → ‘常量表中的常量值’
本实验中的Mini语言Parser使用递归下降分析方法构建。根据老师上课的PPT,其基本思想是:对每一个语法成分(用非终结符号代表),构造相应的分析子程序,该分析子程序分析相应于该语法成分(非终结符号)的符号串。 根据老师上课的PPT,其分析过程是:从开始符号出发,在语法规则支配下,逐个扫描输入符号串中的符号,根据文法和当前的输入符号预测到下一个语法成分是U时,便确定U为目标,并调用U的分析子程序P(U)工作。在P(U)工作的过程中,又有可能确定U或其它非终结符号为子目标,并调用相应的分析子程序。如此继续下去,直到得到结果。
用伪代码表示如下:
algorithm MiniParser is
input: MiniScanner生成的Token串、Identifier表、Constant表
output:
- 正确:伪AST、‘accepted’
- 错误:子程序调用信息、错误所在行、错误位置指示、错误Token对应的字符串
(利用Python自带的异常机制打印出错时子程序调用信息)
try:
调用子程序进行parse,返回最后一个合法Token在Token串中的序号end
except Exception: (出错,捕获到异常)
打印出错时的子程序调用信息
打印出错位置和具体字符
程序报错退出
else:(未捕获到异常)
if end == Token串的长度:
打印AST
打印‘accepted’
return
else: (Token串末尾出现非法Token)
打印出错位置和具体字符
程序报错退出
十分类似,仅举一例:
algorithm ParseStatement is
<语句> → <声明语句> | <赋值语句> | <IF结构> | <WHILE结构>
- input: 指向当前Token的指针idx
- output:
- 正确:parse完毕后的新指针位置、AST新节点
- 错误:带有idx的异常
在AST中添加表示当前被调用的子程序实体的新的子节点,其父亲是子程序调用者
if idx指向的Token是标识符:
新idx ← ParseAssignment(idx) (调用赋值语句子程序)
elif idx指向'if':
新idx ← ParseIf(idx)
elif idx指向'while':
新idx ← ParseWhile(idx)
elif idx指向变量类型:
新idx ← ParseDefinition(idx) (调用声明语句子程序)
else:
raise Exception(idx)
return 新idx
使用Python第三方库treelib进行构建和打印,但由于子程序数目过多,调用过深,使用命令行打印效果不甚理想,故在第五部分测试中选择性出现。
Mini语言的Parser仅设计唯一的出错出口(主程序),并有两种错误类型
- 定义:调用除ParseSource(Parse源代码,对应于开始符号所在的产生式,相当于子程序之首)外的子程序后发现非法Token,相当于一个合法的句子被非法Token打断
- 处理:打印遇到非法Token前的子程序调用信息、非法Token所在行、位置、对应的字符串
- 举例:输入:while(a == 0) } a = 1; }#
- 定义:当一段合法的语句被parse完毕(即重新调用ParseSource)时,由于合法的语句一定由保留字或标识符开头,若非以上两种情况即定义为非法Token,相当于在一个合法的句子parse完毕后发现非法Token,无法继续parse后续语句
- 处理:打印非法Token所在行、位置、对应的字符串,而不打印子程序调用信息,因为之前的语句已经parse完毕
- 举例: 输入:while(a == 0) { a = 1;}}#
上一次实验的Scanner已通过测试,故不再对词法分析负责的内容进行测试。如:源代码未以#结尾、非法变量名是否会使Scanner报错。 测试计划主要分为两个部分,每个部分包括正确和错误用例及对应输出。 由于测试全部通过,故不再说明预期输出,实际输出即符合预期。