编译原理-学习记录4

编译原理-学习记录4递归直接递归:呈现出U→xUyU\rightarrowxUyU→xUy形式的文法产生式间接递归:具有U⇒∗xUyU\mathop\Rightarrow\limits^*xUyU⇒∗xUy形式的推导(规则)左递归产生式呈

递归

直接递归:呈现出 U → x U y U\rightarrow xUy UxUy形式的文法产生式

间接递归:具有 U ⇒ ∗ x U y U\mathop\Rightarrow\limits^* xUy UxUy形式的推导

(规则)左递归

产生式呈 U → U y U\rightarrow Uy UUy形式

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

(规则)右递归

产生式呈 U → x U U\rightarrow xU UxU形式

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

递归的作用

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

等价文法

对于两个文法 G 1 ,   G 2 G_1,\ G_2 G1, G2,如果L( G 1 G_1 G1)=L( G 2 G_2 G2),则 G 1 G_1 G1 G 2 G_2 G2是等价文法

弱等价:符号和顺序相同(此处涉及弱等价)

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

关于文法构造的问题

运算符结合顺序问题

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

运算符优先级问题

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

文法的实用限制

二义性

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

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

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

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

文法的压缩

1、文法不能含有有害产生式: U → U U\rightarrow U UU
2、文法不能含有多余产生式:一种是从开始符号出发的所有推导都不会用到的产生式(不可达非终结符号),另一种是无法推导出终结符号串的产生式

分析方法简介

自上而下分析

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

自下而上分析

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

ch3.词法分析(1)——有穷自动机

自动机

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

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

对于2型文法(上下文无关语言),使用下推自动机进行识别;而对于3型文法(正则语言),使用有穷自动机进行识别

有穷自动机的形式定义

确定的有穷自动机(DFA)

定义:DFA=(Q, Σ \Sigma Σ, t, q 0 q_0 q0, F)
其中,Q是有穷非空的状态集, Σ \Sigma Σ是有穷的输入字母表,t是映射 Q × Σ → Q Q\times \Sigma\rightarrow Q Q×ΣQ q 0 ∈ Q q_0\in Q q0Q是开始状态,而F ⊆ \subseteq Q是非空终止状态集合

FA的表示

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

例如:DFA A=({
q 1 q_1 q1, q 2 q_2 q2, q 3 q_3 q3, q 4 q_4 q4}, {0, 1}, t, q 1 q_1 q1, {
q 3 q_3 q3, q 4 q_4 q4})以及映射t(图1:状态转换表):

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BRjIkLeE-1601738721064)(C:\Users\蔡三圈\AppData\Roaming\Typora\typora-user-images\image-20201002133836978.png)]


图1 状态转换表

表示共有 q 1 q_1 q1, q 2 q_2 q2, q 3 q_3 q3, q 4 q_4 q4这四种状态,输入为0或1,开始状态为 q 1 q_1 q1,结束状态为 q 3 q_3 q3, q 4 q_4 q4。用圆表示状态,start指向开始状态,双圆表示结束状态,输入导致的状态转换使用箭头表示,即可得到状态转换图(图2):

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Y0wh4Owq-1601738721072)(C:\Users\蔡三圈\AppData\Roaming\Typora\typora-user-images\image-20201002134427608.png)]


图2 状态转换图

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

扩充的映射: t : Q × Σ ∗ → Q t:Q\times\Sigma^* \rightarrow Q t:Q×ΣQ,注意到此处原有映射中的 Σ \Sigma Σ被替换为 Σ ∗ \Sigma^* Σ,即此时能够接受符号串,而不仅局限于来源于字母表中的单个符号

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

非确定的有穷自动机

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

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

FA的构造

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

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

NFA到DFA的转换

NFA的确定化

基本思想

到达的状态

FA的构造

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

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

今天的文章编译原理-学习记录4分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/87663.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注