语法分析

算数表达式的上下文无关文法

干什么用?

教材中在语法分析一章首先提出的概念就是上下文无关语法CFG

语法分析器不能没有CFG,正如词法分析器不能没有正规式

也就是说,模式的形式化描述

正规式规定死了,一种语言可能使用的单词有什么

CFG就是规定死了,一种语言可能使用的语句有什么

CFG是一种语言的范式,而满足这个CFG的一句话是该种语言的实例

这就好比:规定汉语的语句是由主谓宾构成的,这相当于立法,就是定义CFG

"我吃饭"就是满足法律要求的:主(我) 谓(吃) 宾(饭),这就是汉语语句的一个实例

判断"我吃饭"是否合法的过程,就是将一条语句展开成多个部分的过程,

判断编程语言的一条语句是否合法,就尝试使用CFG规定的规则推导之

长什么样?

以基本算数运算为例子,分析一个含有加减乘除括号的表达式,其CFG如何定义

CFG由一个状态四元组(非终结符集,终结符集,产生式集,开始符号)构成

最初粗浅的考虑是这样的 $$ \[\begin{aligned} Context Free Grammar&=(Nonterminals,Terminals,Productions,Start Symbol)\\ &\begin{cases} Nonterminals=\{Expression\}\\ Terminals=\{+,\times,(,),id\}\\ StartSymbol=Expression\\ \begin{aligned} Production&:Expression\rightarrow\begin{cases} Expression+ Expression\\ Expression\times Expression\\ (Expression)\\ -Expression\\ id \end{cases} \end{aligned} \end{cases} \end{aligned}\]

$$ Nonterminals集合中只有Expression,意思是,只要是Expresion符号,都可以继续推导

Terminals集合中有所有的运算符,还有一个字面量id,这意味着,推导到最具体的了,不能再具体了

StartSymbol=Expression,这意味着,最开始的时候将整个语句视为一个表达式

怎么干活?

"通过推导的方法可以从CFG产生语言"

实际上就是根据Production产生式集中的合法规则,将抽象的Expression全都替换成具体的id的过程

啥意思呢?举个例子,比如对于1+2+3,一开始的时候StartSymbol="1+2+3",这个整体是一个表达式Expression \[ \begin{aligned} exp(1+2+3)&\rightarrow exp(1)+exp(2+3)\\ &\rightarrow id(1)+exp(2)+exp(4)\\ &\rightarrow id(1)+id(2)+id(3) \end{aligned} \] 这就是左推导的过程,也就是化抽象为具体的过程

严谨吗?

前面这种定义CFG的方法是不严谨的,这么说的原因有两个,

一是是没有体现运算符的优先级,二是没有体现运算符的结合性

优先级

举例1+2*3

按照原来的CFG定义,$exp(1+2)\times exp(3)$和$exp(1)+exp(2\times 3)$两种推导路线都是合法的,这就产生了二义性

结合性

举例1+2+3

按照原来的CFG定义,$exp(1+2+3)\rightarrow exp(1+2)+exp(3)$和$exp(1+2+3)\rightarrow exp(1)+exp(2+3)$都是合法的,这就产生了二义性

消除二义性

如何消除二义性?保证每个表达式后续的推导,只有唯一的路线 $$ \[\begin{aligned} Context Free Grammar&=(Nonterminals,Terminals,Productions,Start Symbol)\\ &\begin{cases} Nonterminals=\{Expression,Term,Factor\}\\ Terminals=\{+,\times,(,),id\}\\ StartSymbol=Expression\\ \begin{aligned} Production\begin{cases} \begin{aligned} Expression&\rightarrow Expression+Term\ |\ Term\\ Term&\rightarrow Term\times Factor\ | \ Factor\\ Factor&\rightarrow (Expression)\ |\ -Factor\ |\ id \end{aligned} \end{cases} \end{aligned} \end{cases} \end{aligned}\]

$$ 如何体现优先级?

$Expression$全部展开之后得到的是$Term1+Term2+Term3+...$只有这一种情况,

也就是说,将Expression视为若干乘式的和,每个乘式再各自计算自己的值后上报给加法.

想要计算加法就必须等所有的乘式落实之后才可以进行.这就体现了先乘后加的优先级

如何体现结合性?

$Expression\rightarrow Expression+Term\ | \ Term$

这意味着,要计算顶层的加法,首先需要计算子Expression的值,

而子Expression相当于是,顶层Expression将最右侧的$+Term$给踢出去.

这就体现了左结合

教材上将上述两点归纳:

1.引入新的非终结符,增加一个子结构并提高一级优先级

2.递归非终结符在产生式中的位置,反应文法符号的结合性

这个归纳纯粹属于是懂得一看就懂,不懂得看了也不懂的那种

甚至"递归非终结符在产生式中的位置"啥意思我也不懂

这是在算数表达式中消除二义性,

实际上在编程语言中还要考虑一个分支结构的特殊性

if-elif-else结构中的匹配原则,就近还是就远原则等等

这是后话

自上而下语法分析

树形结构?

由CFG可以建立两种长得差不多的树形结构,

分析树和语法树,

或者说具体语法树和抽象语法树

以1+2*3为例,推导该表达式的过程为 \[ \begin{aligned} exp(1+2\times 3)&\rightarrow exp(1)+term(2\times 3)\\ &\rightarrow term(1)+term(2)\times fact(3)\\ &\rightarrow fact(1)+fact(2)\times id(3)\\ &\rightarrow id(1)+id(3)\times id(3) \end{aligned} \]

分析树(具体语法树)

flowchart
PLUS1((+))
MULT((*))
EXP123(("exp(1+2*3)"))
EXP1(("exp(1)"))
TERM23(("term(2*3)"))
TERM1(("term(1)"))
TERM2(("term(2)"))
FACT3(("fact(3)"))
FACT1(("fact(1)"))
FACT2(("fact(2)"))
ID3(("id(3)"))
ID1(("id(1)"))
ID2(("id(2)"))

EXP123----EXP1
EXP123----PLUS1
EXP123----TERM23
EXP1----TERM1
TERM1----FACT1
FACT1----ID1

TERM23----TERM2----FACT2----ID2
TERM23----MULT
TERM23----FACT3----ID3

语法树(抽象语法树)

graph
1((1))
	2((2))
	3((3))
	mul((*))
	plus((+))
	plus----1
	plus----mul
	mul----2
	mul----3

两种树的区别

抽象语法树中,叶子节点都是字面量,不能再推导,内部节点肯定都是运算符.

求值时当前节点只需要根据自己的运算规则,取出左右儿子递归运算值,算一下然后交给父节点

咱也不知道这具体语法树有什么作用,明明抽象语法树简洁清晰并且也能完成功能

状态转移图和EBNF

一眼丁真

状态转移图实际上就是为了形式化地得到EBNF,要是能够从本来的文法直接看出EBNF文法,则不需要状态转移图

对于表达式这种简单的文法,直接就能看出EBNF来 \[ \begin{aligned} Expression&\rightarrow Term\ \{(+|-)Term\}\\ Term&\rightarrow Factor\ \{(\times |/) Factor\}\\ Factor&\rightarrow (Expression)\ |\ id\ |num \end{aligned} \] 其中

花括号{}中的内容可以重复0次或者若干次,相当于星闭包

怎么理解文法的EBNF表示呢? \[ \begin{aligned} Expression &\rightarrow Term\ \{(+|-)Term\}\\ &\rightarrow Term±Term±Term±...±Term \end{aligned} \] 也就是说Expression至少由一个Term组成,还可以是若干个Term的加减组成

一眼看不出来咋办?

现在已经知道的是文法规则 \[ \begin{aligned} Language&\rightarrow Expression;Language|\epsilon\\ Expression&\rightarrow Term\ Expression'\\ Expression'&\rightarrow +Term\ Expression'|\epsilon\\ Term&\rightarrow Factor \ Term'\\ Term'&\rightarrow \times Factor\ Term'|\epsilon\\ Factor&\rightarrow (Expression)|-Factor|id \end{aligned} \]

要求出文法的EBNF表示.

眼神不好,不能一眼丁真,就得借助状态转移图

怎么由原来的文法翻译成状态转移图?

以Language为例子:

flowchart LR
0((0))
1((1))
2((2))
3((3))
Language ---->0--Expression-->1--";"-->2--Language-->3
0--ε-->3
style 3 fill:red

推导式中的所有符号,比如Language,Expression等,都作为有向图上的边,代表状态转移.状态作为节点

显然目前建立的所有有向图都是没有圈的,因为目前的文法定义已经消除了所有直接或者间接的左递归,表现到图上就是没有强连通分量

又如对于Expression和Expression'

flowchart LR
4((4))
5((5))
6((6))
Expression-->4--Term-->5--"Expression'"-->6

flowchart LR
7((7))
8((8))
9((9))
10((10))
Expression'-->7--+-->8--Term-->9--Expression'-->10
7--ε-->10

下面就是化简状态转移图,怎么化简?

对于Expression',有一个规则1:

标记为A的边可等价为标记ε的边转向A转换图的初态；

flowchart LR
7((7))
8((8))
9((9))
10((10))
7--ε-->10
Expression'-->7--+-->8--Term-->9
9--ε-->7
style 10 fill:red

然后紧接着可以应用规则2:

ε两头的节点可以合并,也就是说,epsilon闭包中的节点算成一个点

flowchart LR
7((7))
8((8))

Expression'-->7--+-->8--Term-->7

style 7 fill:red

然后紧接着可以应用规则3:

标记相同的路径可以合并

啥意思呢?Expression'现在可以带入到Expression中了

flowchart LR
4((4))

7((7))
8((8))

7--+-->8--Term-->7
Expression-->4--Term-->7
style 7 fill:red

还有一条规则可以继续化简:

不可区分的状态可以合并

这里4状态和8状态都是经过Term转移到7,不可区分,因此有

flowchart LR
4((4))

7((7))


7--+-->4
Expression-->4--Term-->7
style 7 fill:red

此时Expression'已经被扬了,Expression也是不能再简了,这就是最简结构了.根据这个结构,终于一眼丁真了 \[ Expression\rightarrow Term\{+Term\} \]

这里只考虑了加法,减法和加法同级,也容易扩充 \[ Expression\rightarrow Term\{(+|-)Term\} \]

以此类推,可以得到所有符号的EBNF文法 \[ \begin{aligned} Language&\rightarrow \{Expression;\}\\ Expression&\rightarrow Term\{(+|-)Term\}\\ Term&\rightarrow Factor\{(\times |/)Factor\}\\ Factor&\rightarrow (Expression)|id|num \end{aligned} \] 得到该EBNF表示的文法之后,已经可以动手写程序了.

硬编码的代码实现

表达式求值

贴出来又臭又长,不如放到pasbin了递归下降求解表达式 - Pastebin.com

表达式建立语法树

源代码中有反引号,并且博客渲染的时候代码块会匹配最近的反引号,~~这应该是语法分析的错误罢~~

发生代码块反引号匹配错误,只能放到pastbin里了表达式树 - Pastebin.com

将树的结构按照mermaid语法规则输出到tree.md文件,然后用typora打开就可以实现可视化

预测分析

为啥还需要预测分析?

上面我们已经写出代码了,表达式的语法分析可以说已经竣工了,但是为啥本章后面教材还是不依不饶地给了60页?

感觉教材也没有给预测分析器做一个铺垫,直接就抛出了这么一个概念干说.

我觉得,这是因为从EBNF构建语法分析器有很大的局限性,类比一下

根据EBNF写语法分析器,就类似于词法分析器用硬编码的DFA

为什么这样说呢?或者说根据EBNF写代码有啥缺点呢?

首先,EBNF中规定了死了,基本算数运算只有三种优先级,这对应到代码中的三个函数

1
2
3

evalExpression
evalTerm
evalFactor

试想,如果写完程序之后,又想加入新的优先级,比如规定乘方运算的优先级高于乘除低于括号.

又如方括号优先级低于小括号但是高于其他表达式.

这就意味着程序需要大改,新加入evalPower来处理乘方运算,并且函数的调用关系都得改

这就是从EBNF直接写代码的局限性,也就是说可拓展性差

怎么解决呢?还是回顾词法分析中的做法

当时我们也是嫌硬编码的DFA不灵活,于是使用了表驱动或者有向图驱动的DFA.

DFA对外提供三个接口,都屏蔽了自身实现的差异.

表驱动的DFA想要拓展只需要新增表记录就可以了

这就是预测分析器的预测分析表将要干的事情

预测分析器

类比词法分析

前面我们已经给预测分析器做好铺垫了

预测分析器是词法分析器的一种实现方式,是下推自动机的一种实现

ip指向当前输入

这个预测分析器和使用表驱动DFA的词法分析器有一定的相似之处,可以类比理解一下

词法分析器上的状态转移,只需要看一下输入序列,然后去分析表查一下下一个状态就可以了

相比于词法分析器,语法分析器多一个符号栈,也就是说预测分析器上的状态转移,不仅要考虑当前记号流中的记号,还要考虑当前符号栈的状态

没有递归?

同时,从这个类比中,我们也可以隐约发现,预测分析器是没有递归的

之前根据EBNF写的代码,递归很明显,evalExpression->evalTerm->evalFactor

而现在只需要从预测分析表上进行状态转移.消除了递归

这意味着,现在可以将递归的方法,从表达式推广到绘图语言,写"编译原理的实验二--语法分析器"了,

实际上WXQ老师给出了2019C++实现版也就是基于递归下降方法实现的

预测分析表是干啥的?

首先考虑这么一个表达式$id+id\times id$,如果使用前面定义的文法进行匹配,手工做的话应该如何

\[ \begin{aligned} Language&\rightarrow Expression;Language|\epsilon\\ Expression&\rightarrow Term\ Expression'\\ Expression'&\rightarrow +Term\ Expression'|\epsilon\\ Term&\rightarrow Factor \ Term'\\ Term'&\rightarrow \times Factor\ Term'|\epsilon\\ Factor&\rightarrow (Expression)|-Factor|id \end{aligned} \]

\[ \begin{aligned} L&\rightarrow E\\ &\rightarrow TE'\\ &\rightarrow FT'E'\\ &\rightarrow idT'E'\\ &\rightarrow idE'\\ &\rightarrow id+TE'\\ &\rightarrow id+FT'E'\\ &\rightarrow id+idT'E'\\ &\rightarrow id+id\times FT'E'\\ &\rightarrow id+id\times idT'E'\\ &\rightarrow id+id\times id \end{aligned} \]

我们这样做的依据就是文法规则中定义好的推导方式

预测分析表就干了我们脑子干的事情----匹配使用哪个推导规则

先给出这么一个状态转移表,简单地用它分析一下id+id*id,后来再关心这个表是怎么建立的

比如当前栈顶是L,输入符号是id,那么就应该首先L弹栈,然后把符号E压栈,转移到下一个格局

当前栈顶是E,输入符号id,就应该首先E弹栈,然后把TE'压栈,转移到下一个格局

当前栈顶是T,输入id,就应该首先T弹栈,然后FT'压栈,转移到下一个格局

当前栈顶是F,输入id,就应该首先F弹栈,然后id压栈,转移到下一个格局

当前栈顶是id,输入id,匹配成功,都退栈

整个过程中"输入id"一直没变,也就是说指向输入串的指针始终没有移动

这里有一个新名词"格局",实际上类似于状态,它受到当前栈顶,当前输入,预测分析表三者的影响

实际上就是迪杰斯特拉双栈算法求解算数表达式的算法思想

不断压栈直到栈顶和当前符号匹配实际上维护了一个单调栈,越靠近栈顶的符号优先级越高

如何定义格局?

表驱动的词法分析器中定义了一个状态,然后根据当前输入和状态转移表这里两个因素,从当前状态转移到下一个状态

对于预测分析表驱动的语法分析器,定义了一个类似状态的东西叫做"格局",

区别于状态转移,格局转换时需要考虑当前栈顶,预测分析表,当前输入符号,共3个因素

实际上格局变化是状态转移的推广

状态转移时维护一个栈当摆设就成了格局变化

格局如何转移?

设置ip使它指向w的第一个符号，其中ip 是输入指针；
令X=栈顶符号；
while  ( X ≠ ＄ )｛     /   *      栈非空 */ 
            if ( X 等于ip所指向的符号a) 执行栈的弹出操作，将ip向前移动一个位置；
            else  if ( X是一个终结符号)  error ( ) ;
            else  if ( M[X，a]是一个报错条目)  error ( ) ;           
            else  if ( M[X，a] = X →Y1Y2 … Yk  )｛ 
                         输出产生式 X →Y1Y2 … Yk  ；
                         弹出栈顶符号；
                        将Yk，Yk-1 …，Yi 压入栈中，其中Y1位于栈顶。
            }
            令X=栈顶符号
}

这里面M[X,a]就是当前栈顶为X,当前符号为a时查表能够转移到的下一个格局

匹配id+id*id的整个过程如图

语法分析阶段不管是递归下降还是预测分析,其目的相同

1.首先检查有没有语法错误.

2.给出抽象语法树.

递归下降法自顶向下建立抽象语法树是自然而然的

预测分析法怎么建立抽象语法树呢?

一时间竟想不到

蚌埠住了

如何建立预测分析表?

预测分析器算法和文法定义没有关系,文法定义体现在预测分析表上

预测分析器的算法是写死的,但是预测分析表是活的

First集合

$First(\alpha)=\{a|\alpha\Rightarrow a,a\in T\}$也就是$\alpha$可以推导出的一个非终结字符的集合,如果$\alpha\Rightarrow \epsilon$,则$\epsilon \in First(\alpha)$

$First(E)=\{(,id,num\}$

Follow集合

\[ Follow(A)=\{a|S\Rightarrow ...Aa...,a\in T\} \]

紧跟在非终结符A后面的终结符集合

$Follow(E)=\{;,)\}$

算法求解First集合

\[ X\rightarrow \alpha_1|\alpha_2|...|\alpha_m,m\ge1\\First(X)=\cup First(\alpha_i) \]

非终结符的First集合,等于其所有推导的First集合的并集

对于$First(\alpha_i)$的求法:

其中如果$\alpha_i=\epsilon$,则$\epsilon\in First(\alpha_i)$

否则,假设$\alpha_i\Rightarrow Y_1,Y_2,...,Y_n$

如果$Y1$可以推导出$\epsilon$,则Y2就有可能成为最前面的,那么就得考虑$First(Y_2)$

如果$Y_1$推导不出$\epsilon$,则Y2就肯定不可能成为最前面,因此不用考虑$First(Y_2)$ \[ First(\alpha_i)=\cup _{j=1}^k (First(Y_j)-\epsilon) \]

当$Y_k$推导不出$\epsilon$时,才会停止j往后遍历

dustland

语法分析先修-表达式求值