题目描述
本次选做题需要实现一个简单的语法分析器，其文法描述如下：
<程序>→begin <语句> end
<语句>→<赋值语句>│<条件语句>
<赋值语句>→<变量>:=<表达式>
<条件语句>→if <表达式> then <语句>
<表达式>→<表达式>+<变量>│<变量>
<变量>→i
消除左递归
一目了然就可以看到，产生式：<表达式>→<表达式>+<变量>│<变量>存在左递归。
所以第一步要做的是消除左递归，消除结果为：
<表达式>→<变量><表达式1>
<表达式1>→+<变量><表达式1>|ε
到此，文法中的左递归已经完全消除，且满足LL(1)文法。
重命名
为了便于编程，下面对文法中的非终结符用单词替换，如下：
program 程序
statement 语句
assign 赋值语句
condition 条件语句
expression 表达式
expression_1 表达式1
variable 变量
程序实现
根据递归下降编程的思想，上述7个非终结符分别对应7个子函数，其实现的流程图分别如下：
其中：
match(token)函数的作用是用token与当前扫描到的字符(串)进行匹配，匹配成功则返回true
nextsym()函数的作用是使指针item滑动到下一个单词处
program
statement
assign
condition
expression
expression_1
这里需要说明的是，由于产生式<表达式1>→+<变量><表达式1>|ε中含有<表达式1>→ε，故在匹配时如果没有match到其first集中的元素，则接下来需要去match其follow集中的元素，即“end”和“then”，若与follow集中的元素匹配成功，则指针item需要回滚。
variable
测试
我选用了正确和错误的两组共四个测试用例对程序进行了测试，测试结果如下：
正确样例
错误样例
可以看到，程序能够成功识别该文法的语言并给出正确的反馈信息！
