程序实现，使用match函数匹配符号并报错或读取下一个符号

算术表达式的文法形式简单，非终结符具有较少的候选式。当文法产生式形式比较复杂时，难以简单地将匹配工作分配给相应的候选式。通过计算不同候选式的FIRST集，可以快速、准确地进行自上而下的分析。

一般地，假设文法非终结符A的产生式形如A→α1|α2|…|αn。关于A的子程序需要完成以下任务：

（1）检查当前输入符号以确定使用A的哪个候选式。如果输入符号a属于FIRST（αi），则选择αi进行推导，生成语法树中A的下一层结点。

（2）如果输入符号不属于FIRST（A），但有ε∈FIRST（A）。那么，判断输入符号是否属于FOLLOW（A），如果属于，A将自动匹配；否则，就认为输入串出现了语法错误。

对于非终结符A的任一候选式αi，假设αi形如β1β2…βn，则需要依次处理αi中的每个文法符号βi。此时，需要根据βi是终结符或非终结符分别采取不同的方法。如果βi是终结符，则判断其是否与当前的输入符号匹配。使用4.3.2节的match函数，若匹配，则读取下一个输入符号；否则报告错误。此外，如果βi是非终结符，则调用该非终结符相应的子程序βi（）。

非终结符A及其任一候选式αi的子程序如下面代码所示。

扩展BNF改变了文法的形式。就算术表达式的扩展BNF来说，如何保持表达式的左结合性是程序设计过程中需要考虑的问题。以产生式E→T{+T}为例，可以通过在循环过程中将上一次循环构建的子树作为本次循环构建的子树的左子树，实现加法运算的左结合性。(https://www.xing528.com)

抽象语法树

语法分析树清晰展示了推导的各个步骤以及输入串的语法结构。例如，表达式的语法分析树展示了表达式的运算及其左右操作数的构成方式，如图4-10（a）所示。语法制导的语义分析方法与语句的语法结构直接相关。表达式的含义正是需要将操作数进行相关运算。

有一种更为简单的方法能够表示相同的信息，如图4-10（b）所示。树的根结点为运算符，而左右操作数作为左右子树。这种树是源代码结构的抽象表示，称为抽象语法树。抽象语法树虽然不同于语法分析树，但是却包含了进行语义分析的全部信息。语法分析程序通过语法分析树展示了所有语法分析步骤，但通常将构造出一棵抽象语法树。

图4-10　表达式i+i*i的语法分析

例如，下述伪代码将实现算术表达式的语法分析，并为其构建抽象语法树。为了便于理解程序，函数match采用了字符串类型的形参。