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报错。 测试计划主要分为两个部分，每个部分包括正确和错误用例及对应输出。 由于测试全部通过，故不再说明预期输出，实际输出即符合预期。