递归

直接递归：呈现出$U\to xUy$形式的文法产生式

间接递归：具有$U\stackrel{\ast }{\Rightarrow }xUy$形式的推导

（规则）左递归

产生式呈$U\to Uy$形式

如果是经过多步推导得到，则称之为文法/间接左递归

（规则）右递归

产生式呈$U\to xU$形式

同左递归，如果是多步推导得到的，则称之为文法/间接右递归

递归的作用

使用有限的产生式，描述无限的句子——用有穷表示无穷

等价文法

对于两个文法$G_1,G_2$，如果L($G_1$)=L($G_2$)，则$G_1$与$G_2$是等价文法

弱等价：符号和顺序相同（此处涉及弱等价）

强等价：符号、顺序和语义都相同

关于文法构造的问题

运算符结合顺序问题

左递归和右递归，对应左结合和右结合

运算符优先级问题

越靠近语法树下端，运算的优先级越高 优先级更高的运算更晚被推导得到

文法的实用限制

二义性

如果文法G在推导某一个句子的过程中，能够得到两种及以上不同的语法树（无论最左最右推导：最左推导得到的语法树，和最右推导得到的语法树不一样，也算是两种语法树），则称该文法是二义性文法。

消除二义性通常有两种方法： 1、对语义增加限制 2、重新构造一个等价的无二义性文法

通常在if-else语句中，为了提高可理解性，还是使用有二义性文法。通过对语义加上限制来消除二义性

二义性文法不可判定：不存在一个算法，使得能够在有限的步骤内，确切地判定一个文法是否为二义性的

文法的压缩

1、文法不能含有有害产生式：$U\to U$ 2、文法不能含有多余产生式：一种是从开始符号出发的所有推导都不会用到的产生式（不可达非终结符号），另一种是无法推导出终结符号串的产生式

分析方法简介

自上而下分析

从开始符号出发，不断建立直接推导，试图构造一个最左推导序列，最后推导出与输入符号串相同的符号串

自下而上分析

从待输入的符号串开始，利用文法的产生式逐步向上规约，试图规约到文法的开始符号

ch3.词法分析（1）——有穷自动机

自动机

有限状态、有限输入、有开始有结束

是一种能进行运算并实现自我控制的装置

对于2型文法（上下文无关语言），使用下推自动机进行识别；而对于3型文法（正则语言），使用有穷自动机进行识别

有穷自动机的形式定义

确定的有穷自动机（DFA）

定义：DFA=(Q, $\Sigma$, t, $q_0$, F) 其中，Q是有穷非空的状态集，$\Sigma$是有穷的输入字母表，t是映射$Q\times \Sigma \to Q$，$q_0\in Q$是开始状态，而F$\subseteq$ Q是非空终止状态集合

FA的表示

有状态转换表和状态转换图两种表示方式

例如：DFA A=({$q_1$, $q_2$, $q_3$, $q_4$}, {0, 1}, t, $q_1$, {$q_3$, $q_4$})以及映射t（图1：状态转换表）：

图1 状态转换表

表示共有$q_1$, $q_2$, $q_3$, $q_4$这四种状态，输入为0或1，开始状态为$q_1$，结束状态为$q_3$, $q_4$。用圆表示状态，start指向开始状态，双圆表示结束状态，输入导致的状态转换使用箭头表示，即可得到状态转换图（图2）：

图2 状态转换图

DFA的扩充：扩充为能够接受符号串，接受方式为从左到右逐字符接收 例如：对于上述DFA，输入0011，则：t($q_1$, 0011)=t(t($q_1$, 0), 011)=t($q_1$, 011)=……=t($q_1$, 11)=……=t($q_2$, 1)=$q_3\in F$

扩充的映射：$t:Q\times {\Sigma }^{\ast }\to Q$，注意到此处原有映射中的$\Sigma$被替换为${\Sigma }^{\ast }$，即此时能够接受符号串，而不仅局限于来源于字母表中的单个符号

DFA中的“确定”，代表开始状态是唯一的，且输入字母唯一地确定了下一个状态

非确定的有穷自动机

定义：NFA=(Q, $\Sigma$, t, $Q_0$, F) 其中，Q是有穷非空的状态集，$\Sigma$是有穷的输入字母表，t是映射$Q\times \Sigma \to Q$的幂集，$Q_0\in Q$是开始状态集，而F$\subseteq$ Q是非空终止状态集合 注意到与DFA不同的地方：1、映射的右端是Q的幂集（即集合内的元素不再是一个单独的状态，而是可能有多个状态。也就是说，接受输入后，可以到达多个状态）；2、开始状态变为了开始状态集，说明开始状态不再仅仅局限于一个

NFA的扩充 扩充的映射：$t(q,\beta )=t(q,a\alpha )=t(q_1,\alpha )\cup t(q_2,\alpha )...$。其中，$a$是$\beta$中的第一个元素，$q_1,q_2...$是状态$q$接受输入$a$后可能达到的新状态，这些状态的并集就是全部可能到达的状态

FA的构造

1、确定输入字母 2、确定关键状态（模拟识别过程） 3、确定状态间的转换关系 4、确定开始和终止状态

不合法的状态不在图内显示

NFA到DFA的转换

NFA的确定化

基本思想

到达的状态

FA的构造

1、确定输入字母 2、确定关键状态（模拟识别过程） 3、确定状态间的转换关系 4、确定开始和终止状态

不合法的状态不在图内显示