语法解析
语法解析的职责
一个语法解析器有必要能够判断在给定编程语法的状况下,用户编写的程序在语法上是否合理。一般,编程语法需求用某种方式来描绘,下面给出方式化的界说:
- 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→aA\rightarrow a或许A→aBA\rightarrow 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消除能够运用以下办法:


无回溯解析
前面讲到,Top-down leftmost parser在解析时涉及回溯操作,这会降低解析功能。通过引进look-ahead技能,咱们能够消解回溯,做到无回溯解析,对应地,这类语法叫做Backtrack-free grammar,也称作predictive grammar。在介绍无回溯解析算法前,先引进两个概念:First-set、Follow-set。
- First-set 关于特定语法字符 \alpha,First()First(\alpha)是一个调集,包括一切从\alpha动身,运用语法替换规矩生成的句子的首部停止字符。
- Follow-set 关于给定的字符变量\alpha,Follow()Follow(\alpha)是一个调集,包括一切运用语法替换规矩生成的句子中跟着\alpha立即呈现的停止字符。
First-set 具有如下性质:
下面给出一个核算First-set的算法:

咱们试着给出前面表达式语法的First set:
Expr | Expr’ | Term | Term’ | Factor | |
---|---|---|---|---|---|
First | (,name,num | +,−,+,-,\epsilon | (,name,num | ∗,/,*,/,\epsilon | (,name,num |
假如只运用First set,或许会呈现一个问题:look-ahead字符不在First调集中怎么办,直接回来语法错误?这儿的关键在于对\epsilon的处理上,替换规矩\epsilon意思是跳过当时字符变量,转入其他替换规矩中,可是从first-set的界说上能够看出,并不关心跳转操作,所以咱们运用Follow-set来界说了跳转操作。下面给出核算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_n,假如存在如下条件:
咱们就说具有该规矩的语法是backtrack-free的。根据此,引出两种Top-down解析算法:Recursive-Descent算法、Table-Driven算法。
Recursive-Descent算法
Recursive-Descent的主意是朴素的:关于每个字符变量S,依据给出的语法结构,将其写成对应的一个递归函数,这样以来,咱们就把Backtrack-free grammar转换为多个相互调用的递归函数组合,下面给出一个完成比如:
序号 | Production | First+First^+ |
---|---|---|
2 | Expr′→+TermExpr′Expr’\rightarrow + \text{ }Term\text{ }Expr’ | {+}\left \{ + \right \} |
3 | ∣−TermExpr′ \mid – \text{ }Term\text{ }Expr’ | {−}\left \{ – \right \} |
4 | ∣\mid \epsilon | {,eof,)}\left \{ \epsilon,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解析算法:

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

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