1 / 42
文档名称:

编译原理-语言与自动机.ppt

格式:ppt   大小:1,146KB   页数:42页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

编译原理-语言与自动机.ppt

上传人:iris028 2021/1/20 文件大小:1.12 MB

下载得到文件列表

编译原理-语言与自动机.ppt

文档介绍

文档介绍:上次课程内容回顾
一、二义性与二义性的消除
造成二义性的原因-文法符号缺乏明确的优先级和结合性
消除二义性的方法:
改写二义文法为无二义文法
为文法符号规定优先级和结合性
改变语言的结构或书写方式
二、语言与文法的分类
正规式、CFG、CSG
计数问题
1
形式语言与自动机简介
对0型文法施加以下第i条限制,即得到i型文法。
G的任何产生式α→β(S→ε除外)满足|α|≤|β|;
G的任何产生式形如A→β,其中A∈N,β∈(N∪T)*;
G的任何产生式形如A→a或者A→aB(或者A→Ba),其中A和B∈N,a∈T。 ■
若文法G=(N,T,P,S)的每个产生式α→β中,均有α∈(N∪T)*,且至少含有一个非终结符,β∈(N∪T)*,则称G为0型文法。
2
形式语言与自动机简介(续1)
文法、语言与自动机
文 法
语 言
自 动 机
短语文法 (0型)
短语结构语言
图灵机
CSG (1型)
CSL
线性界线自动机
CFG (2型)
CFL
下推自动机
正规文法 (3型)
正规集
有限自动机
3
形式语言与自动机简介(续2)
L3={anbncn|n≥1}
L3'={ambmcn|m,n≥1} (A→AC A→aAb|ab C→cC|c)
L3''={akbmcn|k,m,n≥1} (a+b+c+ )
L3可用下述CSG描述:
S→aSBC (1)
S→aBC (2)
CB→BC (3)
aB→ab (4)
bB→bb (5)
bC→bc (6)
cC→cc (7)
句子akbkck 的推导:
S =>...=> ak-1S(BC)k-1 (by 1)
=> ak(BC)k (by 2)
=>...=> akBkCk (by 3)
=> akbBk-1Ck (by 4)
=>...=> akbkCk (by 5)
=> akbkcCk-1 (by 6)
=>...=> akbkck (by 7)
结论:CSG、CFG、正规式能力递减
但是:能力越强的文法,其文法的设计和自动机的构造越困难
因此:语法分析仅用到CFG(除特别指出,文法即指CFG )
再考察L3:
4
自上而下语法分析 自上而下分析的一般方法
用推导的方法分析输入序列(记号流):
对任何一个输入序列ω,从S开始进行最左推导,直到得到一个合法的句子或发现一个非法结构。
在推导的过程中,从左到右扫描输入序列,并试图用一切可能的方法,自上而下建立它的分析树。
自上而下分析是一种试探的过程,是反复使用不同产生式谋求与输入序列匹配的过程。
5
自上而下分析的一般方法(续1)
用下述文法分析输入序列ω=cad:
S → cAd
A → ab
| a
问题:
若有A→αβ1|αβ2,(公共左因子),则会虚假匹配和大量回溯;造成分析效率低、语义动作难以恢复、以及出错位置的报告不确切等。
若有A→Aα,(左递归),则死循环使分析无法进行下去。
重写文法:
消除左递归,以避免陷入死循环;
提取左因子,以避免回溯。
6
消除左递归
若文法G中的非终结符A,对某个文法符号序列α存在推导A=+>Aα,则称G是左递归的。若G中有形如A→Aα的产生式,则称该产生式对A直接左递归。 ■
<1> 消除文法的直接左递归
考虑: A→Aα|β 产生的语言:βα*
替换为:A→βA'
A'→αA'|ε 消除了一个直接左递归
7
<1> 消除文法的直接左递归(续1)
A→ Aα1|Aα2|...|Aαm|β1|β2|...|βn
其中αi非空,βj均不以A开始。然后用下述产生式代替A产生式:
若αi为空,则形成一个有环的A产生式
消除直接左递归
A → β1 A' |β2 A' | ...|βn A'
A'→ α1 A' | α2 A' | ... | αm A' |ε ■
输入 G中所有的A产生式(含直接左递归)
输出 等价的不含直接左递归的G'
方法 首先,整理A产生式为如下形式:
8
<1> 消除文法的直接左递归(续2)

E →TE' (1)
E'→+TE'

最近更新

《西溪梵隐志》研究的任务书 2页

管件二车间安全主要培训 29页

北师大版语文九下《明月几时有》ppt课件 27页

算法导论第二版第五章总结 23页

算法合集之《基本数据结构在信息学竞赛中的应.. 14页

简约风格商务模版一 27页

北师大版二年级语文上册《流动的画》PPT课件 23页

北师大版九年级语文上册《挖荠菜》教案 18页

简明大学物理第二版刚体力学基础2 24页

北师大版一年级下册语文《好事情》教学反思 27页

2022年济宁市邹城市国投集团招聘考试试题及答.. 3页

2022年-2023年监理工程师之土木建筑目标控制通.. 17页

北京版六年级下册《小英雄雨来》PPT课件 23页

北京版三年级语文上册《习作》教案及反思 28页

北京版《寻找秋天》教学设计 26页

女性盆底功能障碍性疾病的物理治疗研究进展 5页

筑梦新时代、争做好少年主题班会课件 22页

办公室节能减排措施 31页

等腰梯形的判定 24页

初二语文下册《敬畏自然》教学案例 27页

初中语文《过故人庄》教案设计 27页

初三上册语文《傅雷家书两则》教案 31页

初一班语文教师工作总结 26页

创想未来教学设计 31页

参与项目证明书 5页

事态升级管理办法 3页

(完整word版)九宫格数独题目(打印版) 120页

餐厅服务员服务中注意事项100条 7页

经典话剧剧本《雷雨》 15页

攸县一中高一创新班物理试题(共4页) 4页