LL解析器是一种自上而下的解析器,用于根据一定的文法规则和语法分析表来分析和解释输入的代码或语句。LL表示"Left-to-right, Leftmost derivation",即从左到右,最左推导。LL解析器是通过从左到右扫描输入并试图按照文法规则进行最左推导来解析输入。它使用LL文法,其中L表示从左到右扫描输入,第一个L表示对于某个非终结符号,从左向右选择一个产生式进行推导。
LL解析器通常由两个主要的组件组成:预测分析表和递归下降分析器。预测分析表是一个二维表,其中行表示文法规则的非终结符号,列表示输入的终结符号和特殊结束符号。表中的每个表项指示了在给定的非终结符号和输入终结符号的情况下应该采取什么动作(如选择哪个产生式进行推导、移入还是归约),或者是否出现语法错误。递归下降分析器根据预测分析表进行解析,使用递归函数来按照文法规则进行推导。
First()、
对于一个文法的非终结符号,它的First集包含了所有可能的终结符号,即该非终结符号能够推导出的第一个终结符号的集合。计算First集的方法是:
- 如果该非终结符号可以直接推导出一个终结符号,那么将该终结符号加入到First集中。
- 如果该非终结符号可以直接推导出ε(空串),那么将ε加入到First集中。
- 如果该非终结符号可以直接推导出其他非终结符号,那么将该非终结符号的First集中的所有终结符号加入到当前非终结符号的First集中。
Follow()、
对于一个文法的非终结符号,它的Follow集包含了所有可能紧随在该非终结符号之后的终结符号,即该非终结符号在推导过程中可能出现的终结符号的集合。计算Follow集的方法是:
- 将文法的开始符号的Follow集中加入特殊符号$(表示输入的结束)。
- 对于每个产生式 A -> αBβ,将B的Follow集中的所有终结符号加入到β的First集中,除非β可以推导出ε(空串),那么将A的Follow集中的所有终结符号加入到B的Follow集中。
如:S->(L) | aL | LC
找Follow的几种种情况:
- 先在候选式(右边)中找到该非终结符,如L(注意例中只有一个定义,但找Follow要看到所有右边出现该非终结符的)
- 如果L的右边是终结符, 那么这个终结符加入L的Follow
- 如果L的右边是非终结符, 那么把这个非终结符的First除去空加到L的Follow中
- 如果L处在末尾,那么,'->'左边符号的Follow成为L的Follow
- 另外要注意的是:开始符号的Follow中要加上‘#’
构建parsing table、
LL(1)parsing、
确定是不是LL(1)语法、
Comments NOTHING