语法解析

语法解析的职责

一个语法解析器有必要能够判断在给定编程语法的状况下，用户编写的程序在语法上是否合理。一般，编程语法需求用某种方式来描绘，下面给出方式化的界说：

• Context-free grammar：CFG是用来描绘怎么构成句子的一系列规矩的调集
• Sentence：依据CFG生成的字符串
• Production：CFG中的每条规矩称为production
• Nonterminal symbol：production中的字符变量，能够被规矩替换
• Terminal symbol：句子中呈现的单词，实际上是句法分析生成的Token
• Start symbol：grammer中的开始字符变量

描绘表达式的语法比如

1 Expr     -> Expr + Term
2          |  Expr - Term
3          |  Term
4 Term     -> Term * Factor
5          |  Term / Factor
6          |  Factor
7 Factor   -> ( Expr )
8          |  num
9          |  name

Expr是咱们的开始字符，Term、Factor是字符变量，num、name是咱们的Token。关于每条规矩，便利起见，次序编了序号。现在看看咱们依据界说的语法能够生成些什么？顺次运用规矩1->3->6->8->4->6->9->7->2->3->6->9->6->8,终究生成的表达式为4+a*(b-7)。这个进程能够运用语法生成树来表明：

解析

解析与生成的进程相反：给定特定的sentence，咱们需求构建出这棵语法生成树。依据构建进程能够将解析器分为两大类：

• Top-down parsers 从根节点动身，终究生长到叶子结点，在构建进程中，解析器会运用替换规矩，将每个字符变量结点替换为一棵子树，直到一切叶子结点都不再可替换为止。
• Bottom-up parsers 从叶子结点动身生长到根节点，在构建进程中，解析器寻觅满意替换规矩的父结点，随后将该结点参加树中。

无论哪种解析办法，其中都涉及到替换规矩的挑选，不好的挑选会对解析功能产生严峻的影响，因而，合理高效的挑选机制是解析算法的研讨要点。

依照解析复杂度，咱们能够把CFG(Context free grammar)分为4层：

• 任意CFG 没有限制条件的CFG，解析时间复杂度高达O(n^3)

• LR(1) 这类解析器运用自底向上算法，从左向右解析，根据当时字符，每次朝前看至多一个token。

• LL(1) 该类解析器是LR(1)的子集，运用自顶向下算法，从左向右解析，每次朝前看至多一个token。

• RG Regular grammar是一类特别的CFG，替换规矩只要两种：$A\to a$或许$A\to aB$,其中a为停止字符，A、B为字符变量。

简直一切的编程语言结构都能够运用LR(1)方式表达，LL(1)方式更为常见。

从顶向下解析

通用算法描绘

上面给出了一种通用地从顶向下的左替解析算法，root表明根节点，focus表明当时替换规矩中最左边的字符，算法运用数据栈存储替换规矩中待匹配的字符，word表明当时的输入字符。首要进行初始化作业，接着进入一个大循环：假如当时字符是可替换地，那么挑选一条规矩替换当时字符，将规矩中待匹配的字符逆序压入栈中，更新focus；假如focus不行替换且匹配到了word，此刻将输入字符序列下一字符读取到word中，弹出栈顶元素，更新focus；假如一切输入字符均已匹配，回来解析树，不然进行回溯操作。

回溯操作一般自底向上逐层进行：假如当时一切替换规矩均替换失利，回溯到上一层，从头进行替换，假如回溯到顶层依然匹配失利，此刻回来语法错误提示。回溯实际上是对整个语法结构的遍历，这会消耗很多时间，假如有某种算法能够避免回溯，这将大大提高解析功能。

语法结构性问题

将通用算法应用到咱们本篇界说的表达式语法结构上，此刻假如咱们每次替换规矩都选1，会产生什么事情呢？算法不会停止！这种现象称为Left-recursion。解决办法也很简单，咱们能够重写语法替换规矩，使得语法结构是Right-recursion即可：

Expr  -> Term Expr'
Expr' -> + Term Expr'
      |  - Term Expr'
      |  \epsilon
Term. -> Factor Term'
Term' -> * Factor Term'
      |  / Factor Term'
      |  \epsilon

显式Left-recursion消除能够运用以下办法：

Fee′→Fee’\rightarrow\epsilonFee′→的效果是停止替换，假如没有这条规矩，Fee′→Fee′Fee’\rightarrow \alpha Fee’Fee′→Fee′就会不断循环下去。当然，除了直接显式的Left-recursion，还存在隐式Left-recursion，比如$\to ,\to ,\to$,这终究会导致→+\alpha\rightarrow^+\alpha\delta→+，下面给出一个消除Left-recursion的算法：

算法总体分为两步：首要将一切隐式Left-recursion转换为显式Left-recursion，接着消除显式Left-recursion。隐式Left-recursion能够从图的视点来了解：咱们把一切具有Ai→AjA_i\rightarrow A_j\gammaAi​→Aj​方式的替换规矩表明成有向边，一切的字符变量当做图节点，那么隐式Left-recursion意味着图中有环，明显，隐式Left-recursion转换为显式Left-recursion的进程便是减少环的大小，直到图中只存在长度为1的环。

无回溯解析

前面讲到，Top-down leftmost parser在解析时涉及回溯操作，这会降低解析功能。通过引进look-ahead技能，咱们能够消解回溯，做到无回溯解析，对应地，这类语法叫做Backtrack-free grammar，也称作predictive grammar。在介绍无回溯解析算法前，先引进两个概念：First-set、Follow-set。

• First-set 关于特定语法字符 \alpha，$First()$是一个调集，包括一切从\alpha动身，运用语法替换规矩生成的句子的首部停止字符。
• Follow-set 关于给定的字符变量\alpha，$Follow()$是一个调集，包括一切运用语法替换规矩生成的句子中跟着\alpha立即呈现的停止字符。

First-set 具有如下性质：

下面给出一个核算First-set的算法：

算法仍是很直观地：首要核算停止字符的First-set，关于非停止字符来说，假如存在替换规矩A→,=12…kA\rightarrow\beta,\beta=\beta_1\beta_2…\beta_kA→,=1​2​…k​，那么First(A)⊇First(1)First(A)\supseteq First(\beta_1)First(A)⊇First(1​)。考虑1\beta_11​包括\epsilon的状况，此刻First(A)⊇First(2)First(A)\supseteq First(\beta_2)First(A)⊇First(2​)，以此类推，直到核算完一切i\beta_ii​为止。

咱们试着给出前面表达式语法的First set：

Expr	Expr’	Term	Term’	Factor
First	(,name,num	$+,-,$	(,name,num	$\ast ,/,$	(,name,num

假如只运用First set，或许会呈现一个问题：look-ahead字符不在First调集中怎么办，直接回来语法错误？这儿的关键在于对\epsilon的处理上，替换规矩\epsilon意思是跳过当时字符变量，转入其他替换规矩中，可是从first-set的界说上能够看出，并不关心跳转操作，所以咱们运用Follow-set来界说了跳转操作。下面给出核算Follow-set的算法：

有人或许有点模糊：为啥这儿只更新了Follow(\beta),Follow(A)呢？这是因为A呈现在替换规矩的左边，咱们无处得知与A所相关的结构信息，该信息只能从替换规矩的右边获取。要想更新Follow(A),咱们要找到如下规矩：B→1…A…nB\rightarrow\beta_1…A…\beta_nB→1​…A…n​。 前面表达式语法的Follow set：

Expr	Expr’	Term	Term’	Factor
Follow	eof,)	eof,)	eof,+,-,)	eof,+,-,)	eof,+,-,*,/,)

结合First set与Follow set，咱们给出关于规矩的First set界说：

关于任意的替换规矩A→1∣2∣…∣nA\rightarrow\beta_1|\beta_2|…|\beta_nA→1​∣2​∣…∣n​，假如存在如下条件：

咱们就说具有该规矩的语法是backtrack-free的。根据此，引出两种Top-down解析算法：Recursive-Descent算法、Table-Driven算法。

Recursive-Descent算法

Recursive-Descent的主意是朴素的：关于每个字符变量S，依据给出的语法结构，将其写成对应的一个递归函数，这样以来，咱们就把Backtrack-free grammar转换为多个相互调用的递归函数组合，下面给出一个完成比如：

序号	Production	First+First^+First+
2	Expr′→+TermExpr′Expr’\rightarrow + \text{ }Term\text{ }Expr’Expr′→+TermExpr′	$\left\{+\right\}$
3	∣−TermExpr′ \mid – \text{ }Term\text{ }Expr’∣−TermExpr′	$\left\{-\right\}$
4	$\mid$	$\left\{,eof,)\right\}$

Eprime()
    /*Expr'-> + Term Expr' | - Term Expr'*/
    if (word = + or word = -) then begin;
        word <- NextWord();
        if (Term())
            then return EPrime();
            else return false;
        end;
        else if (word = ) or word = eof)
            then return false;
            else begin;
                report a syntax error;
                return false;
            end;   

Table-Driven LL(1) Parser

根据数据栈和二维表，同样能够完成Top-down解析算法：

数据栈保存待生成拜访的节点，二维表保存语法结构一切的look-ahead信息。focus表明待生成的解析树节点，word表明输入字符流当时读取字符。首要初始化作业，将eof，开始字符S压入栈中，focus初始化为S。接着进入一个大循环：依据focus不同方式，执行不同逻辑，这儿分为两部分：悉数匹配成功退出阶段、单叶子结点匹配阶段、解析树扩展阶段。

• 解析树扩展阶段 focus为非停止字符变量，此刻查二维表T，查找替换规矩成功，则进行子树生成，弹出栈顶元素，将替换规矩右手一切非\epsilon字符按从右到左次序压入栈中。查找失利回来错误扩展信息。
• 单叶子结点匹配阶段 focus为停止字符，假如focus与word匹配，则弹出栈顶元素，word更新为下一输入字符。不然回来匹配失利信息。
• 悉数匹配成功退出阶段 focus为eof且word为eof，回来匹配成功信息，退出循环。

关于二维表的构建，流程如下：

关于满意backtrack-free条件的语法结构，构建二维信息表时间复杂度为$O(|P||T|)$,其中P为规矩调集，T为停止字符调集。假如不满意backtrack-free条件，此刻表中元素呈现多条规矩，这需求咱们运用left-factor技能优化语法，使其具有backtrack-free性质。

总结

本篇介绍了语法解析的效果以及解析器的分类，具体说明晰LL(1)解析器的完成算法及细节。Top-down解析算法首要缺陷在于无法解析Left-recursive的语法，尽管能够运用技能手段消解Left-recursive，假如有某种解析算法能够应用到Left-recursive，能够为解析进程节省额外过程，在下篇，咱们会介绍Bottom-up解析相关技能原理，敬请期待。