虎书第3章《语法分析》笔记

缩写

CFG: context free grammar 上下文无关文法
CSG: context sensitive grammar 上下文相关文法

如何理解一个状态数为 N 的自动机无法记忆嵌套深度大于 N 的括号?

匹配括号对于有限自动机是不可识别的.

确定所需匹配的层级时: 可以使用 $[\wedge\{\}]$ 找最内层, 然后反复套娃直到所需层级. 如果要考虑字符串里可能有大括号的话还会更复杂. 通用情形: 不可能. 正则表达式等价于 3 型文法, 只具有相当于有限自动机的表达能力, 而匹配不确定数量的括号对至少需要一个栈, 需要用相当于下推自动机的 2 型文法.

作者:Muchan
链接:https://www.zhihu.com/question/432937087/answer/1606458693
来源: 知乎
著作权归作者所有. 商业转载请联系作者获得授权, 非商业转载请注明出处.

$S \longrightarrow aaS \vert a$ 是什么型的, 为什么?
$S \longrightarrow aSb \vert ab$ 是什么型的, 为什么?
$S \longrightarrow SaS \vert b$ 是什么型的, 为什么?

答: 三种文法都属于上下文无关文法.

四种文法的判断非常简单, 说到到, 四种文法就是规定产生式的左和右边的字符的组成规则不同而已, 其它的不能理解就不要去想了, 你只要知道判断的时候就是以产生式的左边和右边符合的规则进行判断. 下面解释一下如何根据产生式左边和右边的特征来进行判断.

首先, 应该明确, 四种文法, 从 0 型到 3 型, 其规则和约定越来越多, 限制条件也越来越多, 所以, 我们判断时可以从最复杂的 3 型进行判断, 依次向下判断, 如果不符合 3 型的, 那再看是不是 2 型的, 不是 2 型的, 再看是不是 1 型的, 当然, 对于作题作的熟的朋友, 不用这么复杂, 可以一眼直接看出来.

3 型文法遵循什么规范呢?

第一点: 左边必须只有一个字符, 且必须是非终结符;
第二点: 其右边最多只能有两个字符, 且当有两个字符时必须有一个为终结符而另一个为非终结符. 当右边只有一个字符时, 此字符必须为终结符.
第三点: 对于 3 型文法中的所有产生式, 其右边有两个字符的产生式, 这些产生式右边两个字符中终结符和非终结符的相对位置一定要固定, 也就是说如果一个产生式右边的两个字符的排列是: 终结符+非终结符, 那么所有产生式右边只要有两个字符的, 都必须前面是终结符而后面是非终结符. 反之亦然, 要么, 就全是: 非终结符+终结符.

依以上规则判断, 你所给的三个文法显然都不属于 3 型文法.

再看 2 型文法如何判断:

第一点: 与 3 型文法的第一点相同, 即: 左边必须有且仅有一个非终结符.
第二点: 2 型文法所有产生式的右边可以含有若干个终结符和非终结符 (只要是有限的就行, 没有个数限制).

依 2 型文法的判断规则, 你的三个文法都属于 2 型文法, 即: 上下文无关文法.

再看 1 型文法如何判断:

第一点: 1 型文法所有产生式左边可以含有一个, 两个或两个以上的字符, 但其中必须至少有一个非终结符.
第二点: 与 2 型文法第二点相同.

依 1 型文法判断规则, 显然, 你的文法也是属于 1 型的.

最后是 0 型文法, 这个就不用看了, 只要你能描述出来, 都属于这个类型, 即 0 型.

所以, 取其最高的符合规则, 最后的答案是其符合: 上下文无关文法规则, 即 2 型.

本人补充: 一般考试里面分辨 0 型文法 (短语结构文法) 和 1 型文法 (上下文有关文法)!!!

左部长度 > 右部长度一点是 0 型文法 (短语结构文法)

https://blog.csdn.net/qq78442761/article/details/53809926

2 型文法: 又称为上下文无关文法,

式子左边只能有一个字符, 而且必须是非终结符
式子右边可以有多个字符, 可以是终结符, 也可以是非终结符, 但必须是有限个字符

3 型文法: 又称为正规文法 (正规文法又包括左线性文法和右线性文法)

式子左边只能有一个字符, 而且必须是非终结符
式子右边最多有二个字符, 而且如果有二个字符必须是一个终结符和一个非终结符, 如果只有一个字符, 那么必须是终结符
式子右边的格式一定要一致, 也就是说如果有一个是 (终结符+非终结符) 那么所有的式子都必须是 (终结符+非终结符) 如果有一个是 (非终结符+终结符), 那么所有的式子都必须是 (非终结符+终结符)

正规文法——左线性文法:

必须是三型文法
式子右边的产生是 (非终结符+终结符) 的格式

正规文法——右线型文法:

必须是三型文法
式子右边的产生式是 (终结符+非终结符) 的格式

原文链接:https://blog.csdn.net/chen_zan_yu_/article/details/100358554

乔姆斯基体系 The Chomsky hierarchy

https://zh.wikipedia.org/wiki/%E4%B9%94%E5%A7%86%E6%96%AF%E5%9F%BA%E8%B0%B1%E7%B3%BB

乔姆斯基体系是计算机科学中刻画形式文法表达能力的一个分类谱系, 是由语言学家诺姆·乔姆斯基于 1956 年提出的. 它包括四个层次:

0-型文法(无限制文法或短语结构文法) 包括所有的文法. 该类型的文法能够产生所有可被图灵机识别的语言. 可被图灵机识别的语言是指能够使图灵机停机的字符串, 这类语言又被称为递归可枚举语言. 注意递归可枚举语言与递归语言的区别, 后者是前者的一个真子集, 是能够被一个总停机的图灵机判定的语言.
1-型文法(上下文相关文法) 生成上下文相关语言. 这种文法的产生式规则取如 $\alpha A \beta \longrightarrow \alpha \gamma \beta$ 一样的形式. 这里的 $A$ 是非终结符号, 而 $\alpha$, $\beta$ 和 $\gamma$ 是包含非终结符号与终结符号的字符串; $\alpha$, $\beta$ 可以是空串, 但 $\gamma$ 必须不能是空串; 这种文法也可以包含规则 $S \longrightarrow \epsilon$, 但此时文法的任何产生式规则都不能在右侧包含 $S$. 这种文法规定的语言可以被线性有界非确定图灵机接受.
2-型文法(上下文无关文法) 生成上下文无关语言. 这种文法的产生式规则取如 $A \longrightarrow \gamma$ 一样的形式. 这里的 $A$ 是非终结符号, $\gamma$ 是包含非终结符号与终结符号的字符串. 这种文法规定的语言可以被非确定下推自动机接受. 上下文无关语言为大多数程序设计语言的语法提供了理论基础.
3-型文法(正规文法) 生成正则语言. 这种文法要求产生式的左侧只能包含一个非终结符号, 产生式的右侧只能是空串, 一个终结符号或者一个终结符号后随一个非终结符号; 如果所有产生式的右侧都不含初始符号 $S$, 规则 $S \longrightarrow \epsilon$ 也允许出现. 这种文法规定的语言可以被有限状态自动机接受, 也可以通过正则表达式来获得. 正则语言通常用来定义检索模式或者程序设计语言中的词法结构.

正则语言类包含于上下文无关语言类, 上下文无关语言类包含于上下文相关语言类, 上下文相关语言类包含于递归可枚举语言类. 这里的包含都是集合的真包含关系, 也就是说: 存在递归可枚举语言不属于上下文相关语言类, 存在上下文相关语言不属于上下文无关语言类, 存在上下文无关语言不属于正则语言类.

由乔姆斯基谱系描述的集合包含.

下表总结了上述四种类型的文法的主要特点:

文法	语言	自动机	产生式规则
0-型	递归可枚举语言	图灵机	$\alpha \longrightarrow \beta$(无限制)
1-型	上下文相关语言	线性有界非确定图灵机	$\alpha A \beta \longrightarrow \alpha\gamma\beta$
2-型	上下文无关语言	非确定下推自动机	$A \longrightarrow \gamma$
3-型	正则语言	有限状态自动机	$A \longrightarrow aB$

终结符和非终结符

终结符: 通俗的说就是不能单独出现在推导式左边的符号, 也就是说终结符不能再进行推导.

详细一点说: 终结符是一个形式语言的基本符号. 就是说, 它们能在一个形式语法的推导规则的输入或输出字符串存在, 而且它们不能被分解成更小的单位. 确切地说, 一个语法的规则不能改变终结符. 例如说, 下面的语法有两个规则:

x -> xa
x -> ax

在这种语法之中, a 是一个终结符, 因为没有规则可以把 a 变成别的符号. 不过, 有两个规则可以把 x 变成别的符号, 所以 x 是非终结符. 一个形式语法所推导的形式语言必须完全由终结符构成.

非终结符: 不是终结符的都是非终结符. 非终结符可理解为一个可拆分元素, 而终结符是不可拆分的最小元素. 非终结符是可以被取代的符号. 一个形式文法中必须有一个起始符号; 这个起始符号属于非终结符的集合.

判断注意:

只要存在有 S -> L, 则 S 必然是个非终结符
,, [, ], (, ) 这 5 个都是终结符
一般书上把非终结符用大写字母表示, 而终结符用小写字母表示

识别符号: 就是开始符. 由文法产生语言句子的基本思想是: 从识别符号开始, 把当前产生的符号串中的非终结符号替换为相应规则右部的符号串, 直到最终全由终结符号组成. 这种替换过程称为推导或产生句子的过程, 每一步成为直接推导或直接产生.

例如:

有文法 G2[S] 为:

S->Ap
S->Bq
A->a
A->cA
B->b
B->dB

则表示: S 为开始符, S, A, B 为非终结符, 而 p, q, a, b, c, d 为终结符.

还想继续进阶吗? 来道题? 顶得住吗?

原文链接:https://blog.csdn.net/qq_40147863/article/details/88770715

不知道你说的是哪方面的问题. 从终结符与非终结符这两个术语上来看, 应该是编译原理的内容吧. 在编译原理的上下文无关文法中, 终结符可以简单地理解为「推导到这里就终结了」, 也就是说不能再继续通过生成式向下推倒的元素就是终结符. 一般就是实质上的字符. 比如 T->abc. T 推导为串 abc 后已经得到了实质上的字符, 不用在向下推导了. 反过来能够继续推导下去的符号就是非终结符. 比如上文中的 T 他代表的是不确定的某种特征的串, 可以通过生成式被替换成其他的串. 所以叫做非终结符.

作者: 冯昱尧
链接:https://www.zhihu.com/question/20131215/answer/15210544
来源: 知乎
著作权归作者所有. 商业转载请联系作者获得授权, 非商业转载请注明出处.

什么是上下文无关文法?

上下文无关文法

上下文无关文法就是说这个文法中所有的产生式左边只有一个非终结符, 比如:

S -> aSb
S -> ab

这个文法有两个产生式, 每个产生式左边只有一个非终结符 S, 这就是上下文无关文法, 因为你只要找到符合产生式右边的串, 就可以把它归约为对应的非终结符.

上下文有关文法

比如:

aSb -> aaSbb
S -> ab

这就是上下文有关文法, 因为它的第一个产生式左边有不止一个符号, 所以你在匹配这个产生式中的 S 的时候必需确保这个 S 有正确的"上下文", 也就是左边的 a 和右边的 b, 所以叫上下文相关文法.

网友的解读

在上下文无关文法中, 出现在右侧的符号称为终结符, 当生成了一个仅由终结符组成的字符串意味着过程的结束.

上下文无关是指, 一句话的含义与其前后的内容没有或者几乎没有关系, 只由自己决定, 把它剪切到其他任何位置, 也还是原有的意思.

例如:

...
a = 0;
...

这是一个赋值语句, 无论此语句的前后是什么代码, 此语句所代表的操作是确定的. 即:

给变量 a 赋予值 0

换句话说, CPU 遇到什么语句就执行什么语句, 不用管其他的.

编程语言为什么不用人类的语言 (自然语言), 而是用上下文无关的文法呢?
因为

便于设计编译器.
试想一下, 如果可以用自然语言写代码, 那不就是实现了人工智能了吗? 客观上技术目前无法实现.
便于代码开发维护.
如果开发出来的代码像高考的语文阅读理解一样, 每个人都有不同的理解, 那么, 到底哪个才是作者真正想要表达的? 如果人类都确定不了含义, 那计算机同样也确定不了, 最终结果就是错误执行或无法执行.
汇编语言/机器语言是上下文无关的.CPU 执行指令时, 读到哪条执行哪条. 如果 CPU 需要考虑上下文, 来决定一个语句到底要做什么, 那么 CPU 执行一条语句会比现在慢千倍万倍. 考虑上下文的事情, 完全可以用户在编程的时候用算法实现. 既然机器语言是上下文无关的, 那高级语言也基本上是上下文无关的, 可能有某些个别语法为了方便使用, 设计成了上下文相关的, 比如脚本语言的弱类型. 在便于使用的同时, 增加了解析器的复杂度.

综上: 编程语言基本上都采用上下文无关的原则设计语法.

为什么编程语言都是上下文无关文法, 不能采用上下文有关文法吗?

https://www.zhihu.com/question/378230370

为什么要用正则表达式描述词法单词而不用上下文无关文法?

正则表达式以一种静态的, 说明的方式来定义词法结构, 文法以说明的方式来定义语法结构. 但是我们需要比有限自动机更强大的方法来分析文法所描述的语言.

事实上, 文法也可以用来描述词法单词的结构; 但对于此目的, 使用正则表达式要更为合适, 也更为简练.

什么是语法分析树?

语法分析树 (parse tree), 是将一个推导中的各个符号连接到从它推导出来的符号而形成的, 两种不同的推导可以有相同的语法树.

语法分析树是语言推导过程的图形化表示方法. 这种表示方法反映了语言的实质以及语言的推导过程.

定义: 对于 CFG G 的句型, 分析树被定义为具有下述性质的一棵树:

根由开始符号所标记;

每个叶子由一个终结符, 非终结符或 ε 标记;

每个内部节点都是非终结符;

若 A 是某节点的内部标记, 且 X1, X2...Xn 是该节点从左到右的所有孩子的标记. 则:A→X1X2...Xn 是一个产生式. 若 A→ε, 则标记为 A 的节点可以仅有一个标记为 ε 的孩子. 若 A→ε , 则标记为 A 的节点可以仅有一个标记为 ε 的孩子.

以 E => -E => -(E) => -(E+E) => -(id+E) => -(id+id) 为例

语法树

定义:

对 CFG G 的句型, 表达式的语法树被定义为具有下述性质的一棵树:

根与内部节点由表达式中的操作符标记;
叶子由表达式中的操作数标记;
用于改变运算优先级和结合性的括号, 被隐含在语法树的结构中.
说白了, 语法树这玩意, 就一句话: 叶子全是操作数, 内部全是操作符, 树里没有非终结符也不能有括号.

语法树要表达的东西, 是操作符 (运算) 作用于操作数 (运算对象)

分析树与语言和文法的关系

每一直接推导 (每个产生式), 对应一颗仅有父子关系的子树, 即产生式左部非终结符"长出"右部的孩子;
分析树的叶子, 从左到右构成 CFG G 的一个句型 (T, N 两掺的串). 若叶子仅由终结符标记 (+ ,- ,* 之类的运算符号也算是终结符), 则构成一个句子.
推导, 有最左推导和最右推导, 这两种推导方式在推导过程中的分析树可能不同, 但因最终得到的句子是相同的, 所以最终的分析树是一样的.

分析树能反映句型的推导过程, 也能反映句型的结构. 然而实际上, 我们往往不关心推导的过程, 而只关心推导的结果. 因此, 我们要对分析树进行改造, 得到语法树. 语法树中全是终结符, 没有非终结符. 而且语法树中没有括号

在计算机科学中, 抽象语法树 (Abstract Syntax Tree, AST), 或简称语法树 (Syntax tree), 是源代码语法结构的一种抽象表示. 它以树状的形式表现编程语言的语法结构, 树上的每个节点都表示源代码中的一种结构. 之所以说语法是"抽象"的, 是因为这里的语法并不会表示出真实语法中出现的每个细节. 比如, 嵌套括号被隐含在树的结构中, 并没有以节点的形式呈现; 而类似于 if-condition-then 这样的条件跳转语句, 可以使用带有三个分支的节点来表示.

和抽象语法树相对的是具体语法树 (通常称作分析树). 一般的, 在源代码的翻译和编译过程中, 语法分析器创建出分析树, 然后从分析树生成 AST. 一旦 AST 被创建出来, 在后续的处理过程中, 比如语义分析阶段, 会添加一些信息.

分析树和语法树

编译器在实际阅读源程序的时候, 首先通过扫描程序执行语法分析 (Lexical analysis): 它将字符序列收集到称作记号 (token) 的有意义单元中, 记号同自然语言, 如英语中的字词.

例如在下面的代码行中:

a[index] = 4 + 2

这个代码包括了 12 个非空字符, 但只有 8 个记号:

每一个记号均由一个或多个字符组成, 在进一步处理之前它已被收集在一个单元中.

语法分析程序从扫描程序中获取记号形式的源代码, 并定义程序结构的语法分析 (syntax analysis), 这与自然语言中句子的语法分析类似. 语法分析定义了程序的结构元素极其关系. 通常将语法分析的结果表示为分析树 (parse tree) 或语法树 (syntax tree).

例如: 还是那行 C 代码, 它表示一个称为表达式的结构元素, 该表达式是一个由左边为下标表达式, 右边为整型表达式的赋值表达式组成. 这个结构可按下面的形式表示为一个分析树:

请注意, 分析树的内部节点均由其表示的结构名标示出, 而分析树的叶子则表示输入中的记号序列 (结构名以不同字体表示以示与记号的区别).

分析树对于显示程序的语法或程序元素很有帮助, 但是对于表示该结构却显得力不从心了. 分析程序更趋向于生成语法树, 语法树是分析树中所包含信息的浓缩 (有时因为语法树表示从分析树中的进一步抽取, 所以也被称为抽象的语法树 (abstract syntax tree)). 下面是 C 赋值语句的抽象语法树的例子:

抽象语法树和具体语法树有什么区别?

源码算法与数据结构慕容森 2019-07-24 14:49:45

抽象语法树和具体语法树有什么区别?

我一直在阅读有关解释器/编译器如何工作的一些内容, 而我感到困惑的一个领域是 AST 和 CST 之间的区别. 我的理解是解析器生成一个 CST, 将它交给语义分析器, 将其转换为 AST. 但是, 我的理解是语义分析器只是确保遵循规则. 我真的不明白为什么它会实际做出任何改变, 使其变得抽象而不是具体.

有没有关于语义分析器的东西, 或者 AST 和 CST 之间的差异有点人为?

具体语法树以完全解析的形式表示源文本. 通常, 它符合定义源语言的无上下文语法.

但是, 具体的语法和树有很多东西是使源文本明确可解析所必需的, 但却没有实际意义. 例如, 要实现运算符优先级, 您的 CFG 通常具有多个级别的表达式组件 (术语, 因子等), 运算符将它们连接到不同的级别 (您添加术语以获取表达式, 术语由可选乘以的因子组成) 等). 但是, 要实际解释或编译语言, 您不需要这样做; 您只需要具有运算符和操作数的 Expression 节点. 抽象语法树是将具体语法树简化为实际需要表示程序含义的结果. 该树具有更简单的定义, 因此在后续执行阶段更容易处理.

您通常不需要实际构建具体的语法树. 您的 YACC(或 Antlr, 或 Menhir, 或任何......) 语法中的动作例程可以直接构建抽象语法树, 因此具体语法树仅作为表示源文本的解析结构的概念实体存在.

AST 进一步学习

什么是最左推导? 什么是最右推导?

同一个句子可以存在多种不同的推导.

最左推导: 是一种总是扩展最左边非终结符的推导;
最右推导: 下一个要扩展的非终结符总是最右边的非终结符;

(每一步替换最左边的非终结符/每一步替换最右边的非终结符), 最右推导称为规范推导. 最右推导对应于最左规约 (规范规约)

最左推导

定义
在最左推导中, 总是选择每个句型的最左非终结符号.

[句型] 如果 S=》a, 其中 S 是文法 G 的开始符号, 我们可以称 a 是 G 的一个句型, 当 a 是一个终结符时, 此时这个句型可以称为句子.

[非终结符号] 可以继续向下推导的符号

例子
有文法:

E -> E +E | E * E | - E | ( E ) | id

需要推出串 - ( id + id)

根据左推导定义, 有

E => - E => - ( E ) => - ( E + E ) => - ( id + E ) => - ( id + id )

语法树

最右推导

定义
在最右推导中, 总是选择每个句型的最右非终结符号.

例子
有文法:

E -> E +E | E * E | - E | ( E ) | id

需要推出串 - ( id + id)

根据右推导定义, 有

E => - E => - ( E ) => - ( E + E ) => - ( E + id ) => - ( id + id )

版权声明: 本文为 CSDN 博主「爱玩游戏的小隐」的原创文章, 遵循 CC 4.0 BY-SA 版权协议, 转载请附上原文出处链接及本声明.
原文链接:https://blog.csdn.net/qq_40294512/article/details/89363560

推导题目

一,【问题描述】
令文法 G[N]为
G[N]:N→D IND
D→0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
(1) G[N]的语言 L(G) 是什么?
(2) 给出句子 0127, 34 和 568 的最左推导和最右推导.

二,【问题解答】
答:
(1) G[N]的语言 L(G[N]) 是非负整数.
(2) 最左推导: N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127
N=>ND=>DD=>3D=>34
N=>ND=>NDD=>DDD=>5DD=>56D=>568
最右推导: N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127
N=>ND=>N4=>D4=>34
N=>ND=>N8=>ND8=>N68=>D68=>568
————————————————

版权声明: 本文为 CSDN 博主「作业写不完的卑微小 cookie」的原创文章, 遵循 CC 4.0 BY-SA 版权协议, 转载请附上原文出处链接及本声明.
原文链接:https://blog.csdn.net/weixin_44279771/article/details/114533865

什么是二义性文法? 如何消除二义性文法?

如果一个文法能够推导出具有两颗不同语法树的句子, 则该文法有二义性.

二义性文法会给编译带来问题, 通常我们希望文法是无二义性的.

二义性文法转为无二义性文法的方法: 文法转换.

造成二义性的原因是: 文法中没有体现出结合律和优先级

https://www.jianshu.com/p/2d55d50f8bc4

二义性问题

二义性问题: 一个句子可能对应多于一棵语法树.

【例】: 设文法 G: E → E+E | E*E | (E) | -E | id

则, 句子 id+id*id, id+id+id 可能的分析树有:

在该例中, 虽然 id+id+id 的 "+" 的结合性无论左右都不会影响结果. 但万一, 万一"+"的含义变成了"减法", 那么左结合和右结合就会引起很大的问题了.

我们在这里讲的"二义性"的"义"并非语义——我们现在在学习的内容是"语法分析器", 尚未到需要研究语言背后含义的阶段.

"语法"分析的任务, 是确定 "E+E" 这么写是否合法;
"语义"分析的任务, 是确定 "+" 这个符号到底蕴含着什么信息, 即, 该怎么解释这个符号.
我们现在讲的"二义性"指的是一个句子对应多种分析树.

优先级, 结合性: 引起二义性的根本原因

二义性的体现, 是文法对同一句子有不止一棵分析树. 这种问题由【句子产生过程中的某些推导有多于一种选择】引起. 悬空 else 问题就可以很好地体现这种【超过一种选择】带来的二义性问题, 示例如下.

【悬空 (dangling)else】问题

看下面这么个例子..

(其实, 我感觉这个其实比较像是"说话大喘气"带来的理解歧义问题...) 上面的产生式中并没体现出来该咋算分一块, 所以两种完全不同的句子结构都是合法的.

二义性的消除

二义性问题是有救的, 大概有以下这三种办法:

将二义文法改成非二义文法;
规定二义文法中符号的优先级和结合性;
改变语言的结构或书写方式.

这些办法的核心, 其实都是将优先级和结合性说明白.

改写二义文法为非二义文法

核心: 把优先级和结合性说明白

既然要说明白, 那就不能让一个非终结符可以直接在当次推导中能推出会带来优先级和结合性歧义的东西.(对分析树的一个内部节点, 不会有出现在其下面的分支是相同的非终结符的情况. 如果有得选, 那就有得歧义了. 没得选才能确定地一路走到黑)

改写为非二义文法的二义文法大概有下面这几个特点:

需要引入新的终结符, 且新引入的非终结符, 能够限制每一步推导都只有唯一的选择;
引入新的非终结符后, 推到步骤会增多 (分析树增高);
越接近 S 的文法符号优先级越低 (重要!!);
对于 A → αAβ, 若 A 在终结符左侧出现 (即终结符在 β 中), 则 A 产生式具有左结合性;
在语法树中, 越在分析树底下的运算符号越先被计算 (即, 离开始符号越远的越先算).
改写的关键步骤:

引入新的非终结符, 增加一个子结构并提高一级优先级;
若要运算有左结合性, 需要让递归非终结符在终结符左边. 相对的, 递归非终结符在右边则会让运算右结合.
【例】改写下面的二义文法为非二义文法. 图右侧是要达成的优先级和结合性

改写的核心其实就两句话:

要引入新的优先级, 就需要引入新的非终结符, 且距离 S 越近的文法符号优先级越低;
递归非终结符在终结符左边, 运算就左结合, 反之亦.
所以能够得到非终结符与运算的对应关系 (因为不同的运算有不同的优先级, 我们想要引入多个优先级就要引入多个新的非终结符. 这样每个非终结符就可以负责一个优先级的运算符号, 也就是说新的非终结符是与运算有关系的了. 因此这里搞出来了"对应关系"四个字) 如下:

优先级由低到高分别是 +, ,-, 而距离开始符号越近, 优先级越低. 因此在这里的排序也可以+-顺序. 每个符号对应一层的非终结符. 根据所需要的结合性, 则可确定是左递归还是右递归, 以确定新的产生式长什么样子

【例】: 规定优先级和结合性, 写出改写的非二义文法

让我们来搞【悬空 else 】罢!

我们已经掌握了一种叫做【改写】的工具, 能让我们消除二义性. 接下来我们就要用这个工具来尝试搞搞悬空 else 问题!

悬空 else 问题出现的原因是 then 数量多于 else, 让 else 有多个可以结合的 then. 在二义文法中, 由于选哪两个 then, else 配对都可以, 故会引起出现二义的情况. 在这里, 我们规定 else 右结合, 即与左边最靠近的 then 结合.

为改写此文法, 可以将 S 分为完全匹配 (MS) 和不完全匹配 (UMS) 两类. 在 MS 中体现 then, else 个数相等即匹配且右结合; 在 UMS 中 then, else 不匹配, 体现 else 右结合.

【例】: 用改写后的文法写一个条件语句

经过检查, 无法再根据文法写出其他分析树, 故已经消除了二义性

规定优先级和结合性

虽然二义文法会导致二义性, 但是其并非一无是处. 其有两个显著的优点:

比非二义文法容易理解;
分析效率高 (分析树高度低, 直接推导的步骤少).
在 Yacc 中, 我们可以直接指定优先级, 结合性而无需自己重写文法.

%left '+'
%left '*'
%right '-'
left 表示左结合, right 表示右结合. 越往下的算符优先级越高.

嗯就这么简单...

修改语言的语法

我们其实可以把语言本身定义成没有优先级和结合性的.. 然后所有的优先, 结合都交由括号进行控制, 哪个先算就加括号. 把一个过程的结束用明确的标志标记出来.

比如在 Ada 中:

if x<3 then 
    if x>0 then 
        x:= 5; 
    end if;
    else x:= -5;
end if;

在 Pascal 中, 给表达式加括号:

(a+b)>(c*d)

什么是预测分析?

递归下降分析也称为预测分析, 只适合于每个子表达式的第一个终结符能够为产生式的选择提供足够信息的文法.

预测分析器的优点就在于其算法简单, 我们可以用它手工构造分析器, 而无需自动构造工具.

LL(1) 文法分析

Parsing • LL(1) 文法的分析, 以及 First 集和 Follow 集究竟是什么

预测分析法与预测分析表的构造

预测分析法

预测分析法也称为 LL(1) 分析法, 是确定的自上而下分析法, 这种分析法要求文法是 LL(1) 文法.

预测分析表的构造

预测分析器的总控程序对于不同的 L L ( 1 ) LL(1)LL(1) 文法都是相同的, 而预测分析表对于不同的 L L ( 1 ) LL(1)LL(1) 文法是不相同的.

产生式的 SELECT 集

在这里插入图片描述
由 SELECT 集得预测分析表

分析过程

预测分析器如何构造?

参考上面的一节.

如何消除左递归?

对于下面的两个产生式构造预测分析时:

E -> E + T
E -> T

肯定会导致在 LL(1) 分析表中有双重定义的登记项, 因为任何属于 FIRST(T) 的单词同时也属于 FIRST(E+T), 原因是 E 作为 E 的产生式的第一个右部符号出现, 这种情况称为左递归 (left recursion), 具有左递归的不是 LL(1) 文法.

为了消除左递归, 我们将利用右递归来重写产生式. 为此需要引入一个新的非终结符 E', 并将产生式重写为:

E -> T E'
E' -> + T E'
E' ->

什么是提取左因子?

什么是 LR(0) 分析?

https://longfangsong.github.io/lr0/

什么是 LR(0) 的移进和规约?

移进-归约分析
回忆你很可能在大一大二 1 写过的运用栈进行表达式求值的程序, 我们将其简化到只支持加法和乘法, 这里给出一个 Rust 语言的例子 (写的比较随意……), 太长不看党可以直接跳过看下面的分析:

省略 Rust 的代码.

我们以表达式 1 + 2*3 + 4 的求值来观察这一过程:

输入数字 1, 压入栈中

输入操作符'+', 压入栈中

输入数字 2, 压入栈中

输入操作符'*', 压入栈中

输入数字 3, 压入栈中

输入操作符'+', 优先级低于栈中最后一个压入的运算符, 先对栈中内容求值, 再将'+'压入栈中

'*'优先级高于'+', 求值

'+'优先级等于'+', 求值

栈中没有运算符了, 压入'+'

看到数字 4, 压入

没有输入了, 不断求值直到没有更多运算符

这里的 11 就是我们求得得答案.

移进和归约
我们看到, 我们上面的分析过程中出现了两种操作:

移进: 将输入的值或者操作符压入栈中
归约: 将输入的值和栈顶的某几个值经过计算, 变为一般来说更少的几个值, 压回栈中
我们可以将"值","操作符"推广到"文法元素", 得到了文法分析中的移进和归约

移进: 将输入的某个 token 压入栈中
归约: 将输入的值和栈顶的某几个文法元素经过计算, 变为一般来说更少的几个文法元素, 压回栈中
那么我们就能将上面的例子推广到更一般的, 非数字的场景, 以文法 2:

Expr -> id | Expr + Expr | Expr * Expr

和表达式 a + b * c + d 为例 (图中的所有蓝色节点均代表, 其中复杂 Expr 已经画为 AST 的样子):

通过简单地将上面求值中的数字改为了文法元素 (也即 AST 的节点), 我们容易地将表达式求值的方法扩展到了求表达式对应的 AST.

冲突

在移进-归约分析过程中, 可能会遇到某些情况下, 有多种可能使用的行为, 例如:

此时是否应当将 1+2 归约为 3? 这就要等到下一个操作符到来才能决定.

移进-归约冲突
当某个输入可以选择与栈中内容结合, 进行归约, 也可以选择直接压入栈, 后续再进行归约时, 就说我们遇到了一个移进-归约冲突.

上述的例子就是一个典型的移进-归约冲突.

归约-归约冲突
当我们遇到了某个输入与栈中内容结合, 其结构符合多个产生式时, 可以有多种方式进行归约, 这时就说我们遇到了一个归约-归约冲突.

1 我初三就会写了, 你来打我呀 (虽然当年写的爆炸丑陋)
2 这里要注意其实可以说归约时用的产生式是, 这样就没有了优先级这个概念, 但这样就是个上下文有关文法了.

什么是移进规约冲突? 如何消除冲突?

那么, 什么是移进规约冲突呢? 意思就是说, 当我们预读了词素的时候, 既可以对分析栈里面已有的词素进行规约也可以对预读的词素进行移进, 这就是已经规约冲突.

移入--归约冲突: 某一产生式的右部是另一产生式的前缀

归约--归约冲突: 不同产生式有相同的右部或者产生式的右部是另一产生式的后缀

举例如下:

之前我们说过了这个 LR(0) 分析和 SLR(1) 分析, LR(0) 分析是把规约项的对应规则的序号填到所有的非终结符中, 这个 SLR(1) 分析则是把规约项对应规则的序号写到 FOLLOW 集中. 而如果 FOLLOW 集中出现了和移进项的冲突那么就称为移进规约冲突. 即此时的 FOLLOW 集和这个移进项有交集. 那么此时就要采取一种新的分析方法 LR(1) 分析.

LR(1) 分析同上述两种分析方式不同的是添加了一个向前搜索符号. 在搜索符号的前面加上一个","来表示界符.

对于 LR(1) 分析有几项要注意的地方