语言的语法

文法的产生

自然语言：先有语言，后有语法

程序设计语言：先有语法，后有语言

语言的三个基本要素

语法

语义

语用

高级语言语法的表示形式

BNF巴科斯范式
上下文无关文法

文法的定义

一个文法是一个四元组

$$ G=(V_N,V_T,S,P) $$

$V_T$是一个非空的有限集合，它的每个元素称为终极符号或终极符，一般用小写字母表示，从语法分析的角度，终极符号是一个语言不可再分的基本符号。

$V_N$是一个非空的有限集合，它的每个元素称为非终极符号、非终极符或中间符，一般用大写字母表示。非终极符是一个语法范畴，表示一类具有某种性质的符号。设$V$是文法$G$的符号集，则有$V=V_N\cup V_T,V_N\cap V_T=\varnothing$

$S$是特殊的非终极符号，称为开始符号，$s\in V_N$

$P$是产生式的有限集合，所谓产生式，也称为产生规则，是按照一定格式书写的定义语法范畴的文法规则。

上下文无关文法

产生式是形式为

$$ A\to\alpha $$

A:称为产生式的左部，$A\in V_N$
$\alpha$:称为产生式的右部，$\alpha\in (V_T\cup V_N)^*$
$\to$或者$::=$，读作定义为或由…组成
开始符号S必须至少在某个产生式的左部出现一次
为了书写方便，若干个左部相同的产生式，可以合并为一个

$$ P\to\alpha_1|\alpha_2|\cdots|\alpha_n $$

例子：

$ G=\{V_N,V_T,P,S\}$

$V_N=\{N,D\}$

$V_T=\{0,1,2,\cdots,9\}$

$P=\{N\to D,N\to ND, D\to 0|1|\cdots|9\}$

$S=N $

基本概念

直接推导：如果$A\to\beta$是一个产生式，则有，$\alpha_1A\alpha_2\Rightarrow\alpha_1\beta\alpha_2$

$\Rightarrow$:使用一条规则，代替左边的符号，产生右边的符号

一次推导：只能选择一条产生式进行替换，且只能替换一个非终极符

$A\Rightarrow^+\beta$一步或多步

$A\Rightarrow^*\beta$零步或多步

句型：设有文法G，如果有$S\Rightarrow ^*\beta$，则称符号串$\beta$为G的句型。我们用$SF(G)$表示文法G的所有句型集合。通俗一些讲，开始符能经过推导得到的符号串。

句子：设$\beta$为文法G的一个句型，且$\beta$只包含终极符，则称$\beta$为G的句子，句型其实是一种合法的句子结构。开始符能经过有限次推导得到的全为终极符的符号串。

语言：$L(G)=\{u|S\Rightarrow^+u,u\in V_T^*\}$。文法G所定义的语言，是其所有句子的集合。

每一种高级程序设计语言都有自己的语法

符合高级语言文法的程序就是该语法的句子

所有程序组成的集合就构成了语言

语法分析：验证所写程序是否符合语言的文法

验证程序是不是语法的句子

最基本的方法，采用类搜索算法，从开始符出发进行推导。

用剪枝提高效率

自顶向下的语法分析：从开始符出发，根据定义看是否可以推导出程序。

自底向上的语法分析：从程序出发，用规则的左部替换规则的右部，一直到规约成开始符。

短语：设S是文法的开始符，有$S\Rightarrow^*\alpha_1A\alpha_2$，如果有$A\Rightarrow^+\beta$，则称$\beta$是句型$\alpha_1\beta\alpha_2$的一个短语。

简单短语：设S是文法的开始符，有$S\Rightarrow^*\alpha_1A\alpha_2$，如果有$A\Rightarrow\beta$，则称$\beta$是句型$\alpha_1\beta\alpha_2$的一个短语。

句柄：句型中最左简单短语称为句柄

直接左递归：$E\to E\alpha$，则称E是直接左递归

直接右递归：$E\to\alpha E$

左递归：$E\Rightarrow^+E\alpha$

右递归：$E\Rightarrow^+\alpha E$

递归：$E\Rightarrow^+\alpha_1E\alpha_2$

有递归才能有无穷的句子。

最左推导：如果进行推导时，选择的是句型中最左非终极符，则称为最左推导，用符号$\Rightarrow_{lm}$表示。

左句型：用最左推导方式导出的句型，称为左句型。

每个句子都有相应的最左最右推导。（对句型不成立）

文法分类

0型文法

如果对文法G中任意产生式不加任何限制，并且至少含有一个非终极符，则G称为0型文法或短语型语法

1型文法

如果文法G中的任一产生式均限制为$\alpha A\beta\to\alpha\gamma\beta$，A是非终极符

2型文法

$A\to\alpha$上下文无关文法，A为非终极符。

3型文法

$A\to aB$或$A\to a$，AB为非终极符，a为终极符，与自动机等价

例题

语法树

设G是给定的语法，称满足下列条件的树为G的一颗语法树。

树的每个节点都标有G的一个语法符号，且根节点标有初始符S。
如果非叶节点A按从左到右顺序由n个儿子节点，$B_1,\cdots，B_n$，则$A\to B_1\cdots B_n$一定是G的一个产生式。

反映出推导过程，每一步节点生长的过程，都可以对应到我们的一部推导。
语法树反映出串的语法结构。

子树：某语法树T中的某一节点A和它所有分支组成的树$T'$，是T的一颗子树

简单子树：从某一节点A与其子节点（单层节点）组成的树，有且仅有一层子节点。

子树的叶子节点$\Longleftrightarrow$短语

简单子树的叶子节点$\Longleftrightarrow$简单短语

最左边简单子树$\Longleftrightarrow$句柄

语法树所有的叶子节点从左到右连接起来组成的符号串是一个句型。

语法树的子树所有叶节点对应语法符号从左到右连接起来组成的符号串是一个短语。

简单子树所有叶节点对应的语法符号从左到右连接起来组成的符号串是一个简单短语。

最左简单子树节点对应语法符号从左到右连接起来组成的符号串是句柄。

文法的二义性

对于一个文法G，如果至少存在一个句子，有两颗或以上不同的语法树，则称该句子是二义性的，包含有二义性句子的文法称为二义性文法，否则，该文法是无二义性的。

如何消除二义性

文法变换

加入优先级，加入左结合

添加语义规则

二义性的判定

不存在一个一般性方法来判断一个现有文法是否为二义性文法。设计一个画出两个语法树的句子。

二义性的利用

对二义性文法进行修改，消除其二义性会导致文法的复杂度和符号数目迅速升高。可以利用二义性文法状态少，分析快的特点，使用二义性文法，对具体问题加入语义规则，约束其二义性即可。

文法的等价变化

提取公共前缀

消除直接左递归

公共前缀

A的不同产生式的右部具有相同的前缀，这种情形不满足自定向下的语法分析条件。可用提取左因子的方法消除产生式的公共前缀。

经过反复提取左因子，就能够使每个非终极符的不同产生式的右部具有不同的前缀。

消除直接左递归

例题

找在多个串中出现的终极符，然后让其生成方式不同。

自顶向下语法分析概述

程序序列是否能够由开始符经过一系列推导来得到。

每个句子都有相应的最右和最左推导。

非二义性文法，则最左推导的序列唯一。

思想：从文法的开始符出发企图用最左推导推导出与输出的单词串完全相匹配的句子。若输入的单词串使给定文法的句子，则必能推出，反之必然以推导失败终止。

自顶向下语法分析：

非确定的自顶向下语法分析方法
确定的自顶向下语法分析方法：实现方法简单，直观，便于手工构造和自动生成，使目前常用的语法分析方法。
- 递归下降方法
- LL(1)方法

选择规则的策略
- 穷举方法效率非常差
- 考虑更多的信息，如输入流
- 根据输入流选取规则
- 考察输入流中的几个符号

三个集合

Predict集

使用了某条规则$A\to\beta$，产生的所有串的头符的集合。

两种情况：

$\beta \Rightarrow^*\varepsilon$，$\beta$最后能推出空串，我们需要考虑A后面紧接着的串的头符，$Fellow(A)$。
$\beta\not\Rightarrow^*\varepsilon$，$\beta$最后推不出空串，那么我们需要考虑$\beta$能推导出的串的头符，$First(\beta)$。

First集

设$G=(V_T,V_N,S,P)$是上下文无关文法，$\beta\in(V_T\cup V_N)^*$

$First(\beta)=\{a\in V_T|\beta\Rightarrow^*a\cdots\}\cup(if\ \beta\Rightarrow^*\varepsilon \ then\{\varepsilon\}\ else\varnothing)$

Fellow集

设$G=(V_T,V_N,S,P)$是上下文无关文法，$A\in V_N$，S是开始符号

$Follow(A)=\{a\in V_T|S\Rightarrow^+\cdots Aa\cdots\}\cup(if\ S\Rightarrow^*\cdots A\ then\ \{\#\}\ else\ \varnothing)$

$\#$是为了判断结束，人为添加的符号。

Predict集

$$ Predict(A\to\beta)\\=First(\beta),当First(\beta)不含\varepsilon,\\=First(\beta)-\{\varepsilon\}\cup Follow(A),当First(\beta)含\varepsilon $$

简述三个集合

$$ Predict集\Rightarrow一条规则：A\to\beta \\ First集\Rightarrow一个串：\beta \\ Fellow集\Rightarrow 一个非终极符：A $$

First集计算

若$X\in V_T$，$First(X)=\{X\}$
若$X\in V_N$，则$First(X)=\{a|X\to a\cdots\in P,a\in V_T\}$
若$X\in V_N$，且有产生式$X\rightarrow\varepsilon$，则$\varepsilon\in First(X)$
若$X\in V_N$，有产生式$X\to Y_1Y_2\cdots Y_n$，且$Y_1,Y_2,\cdots ,Y_i\in Y_N$
- 当$Y_1,Y_2,\cdots,Y_{i-1}\Rightarrow^*\varepsilon$，则$First(Y_1)-\{\varepsilon\}，\cdots,First(Y_{i-1})-\{\varepsilon\},First(Y_i)$都包含在$First(X)$中。
- 当$Y_i\Rightarrow^*\varepsilon(i=1,2,\dots,n)$，若$i \not= n$，则将$First(Y_{i+1})$并入$First(X)$，否则，将$\{\varepsilon\}$并入$First(X)$中。

Fellow集计算

对所有$A\in V_N$且A非开始符：
- 令$Follow(A):=\{\}$
- 对开始符S:令$Follow(S)=\{\#\}$
若有产生式$A\to xBy$
- 如果$\varepsilon\in First(y)$，则：$Follow(B)=Follow(B)\cup(First(y)-\{\varepsilon\})\cup Follow(A)$
- 否则：$Follow(B)=Follow(B)\cup First(y)$
重复2，直至对所有$A\in V_N$，$Follow(A)$收敛为止
一般情况至少算两遍

非确定的自顶向下语法分析方法主要问题：虚假匹配引起的回溯

由于相同左部的产生式的右部FIRST集的交集不为空而引起的回溯。
由于某非终极符的产生式的右部能推出$\varepsilon$，且该非终极符的FOLLOW集中含有其某个产生式右部的FIRST集中的元素。

至多有一个产生式被选择的条件

任意两个产生式的predict集没有交集。

满足该文法称为LL(1)文法，递归下降子程序文法。

非LL(1)文法到LL(1)文法的等价转换

消除左公共前缀

消除直接左递归

消除左递归

有一定不是，没有不一定是。

LL(1)语法分析原理

从左到右扫描，按最左推导的方式推出输入流。

任意两个产生式的Predict集没有交集，满足这一条件的文法称为LL(1)文法。

LL(1)是LL(k)的特例，其中k表示向前看k个符号。

LL(1)方法和递归下降法属于同一级别的自顶向下分析法。

用LL(1)命名分析法的原因：

第一个L表示，相应语法分析将按自左至右的顺序输入符号串。
第二个L表示，在分析过程中产生一个句子的最左推导。
括号中的1，则表示在分析过程中，每进行一步推导，只要查看一个输入符号便能确定当前所应用的产生式。

语法分析的动作

替换：当分析栈的第一个符号是$V_N$时，就要用规则进行推导，用规则右部将其替换。

匹配：分析栈第一个符号是$V_T$时，与输入流中的第一个符号进行匹配。

成功

出错、失败

LL(1)语法分析原理

LL(1)分析器由输入流，LL(1)分析表，符号栈，驱动程序。

输入流：待分析的符号串

符号栈：存放分析过程的文法符号串

LL(1)分析表：用来表示相应文法的全部信息的一个矩阵

驱动程序：语法分析程序

LL(1)分析表的定义：

$$ T:V_N\times V_T\to P\cup\{Error\} $$

LL(1)表的构造方法

对文法的每一个产生式求predict集
对文法的每个产生式$Predict(A\to \alpha)=(a_1,\cdots,a_n)$
- 令$T(A,a_i)=A\to\alpha$
其他元素为error

驱动程序的设计

分析的初始格局$(S\#,a_1\cdots a_n\#)$

一般格局$(X_1\cdots X_m,a_i\cdots a_n\#)$

设存在格局为$(X_1\cdots X_m,a_1\cdots a_n\#)$

若$X_1\in V_T \& X_1=a_1$，则有$(X_1\cdots X_m,a_1\cdots a_n\#)$
若$X_1\in V_N$则查表，若$T(X_1,a_1)=X_1\to\alpha$，格局为$(\alpha X_2\cdots X_m\#,a_1\cdots a_n\#)$，若$T(X_1,a_1)=error$，则报错。
若格局为$(\#,\#)$，则分析成功
其他情况报错