lr0要不要消除谎言左递归

来源：蜘蛛抓取(WebSpider) 时间：2017-12-25 14:51 标签： 左递归

●翻译、编译、目标语言和源语訁这几个概念的理解

●编译的总体过程：词法分析，语法分析、语义分析与中间代码的生成、代码优化、目标代码的生

成以及伴随着整个过程的表格管理与出错处理。

1、编译过程主要包括五个阶段每个阶段的主要任务是什么？编译程序是否都需要实现这五个阶段（鈈

需要，只有词法分析、语法分析、语义分析和目标代码生成是必要的而中间代码生成和代码优化并不是必须的。）

2、编译方式与解释方式有什么异同

编译方式和解释方式都对源程序进行了翻译，只是前者相当于实际生活中的笔译而后者相当于口译。

虽然有些解释程序对源程序进行了某些形式上的转换但最终并没有生成目标代码。因此两者的根本区别在于是否生成目标代码而不是是否进行了翻译。

●与文法相关的概念：字母表符号及符号串、闭包和正闭包，连接空集，产生式推导，直接

推导归约，句子句型，句柄，語法树语言，最左推导最右推导（规范推导），文法的递归等

●文法的定义：文法是一个四元组：（终结符号集，非终结符号集開始符号、产生式集）。

●用文法来描述语言及通过文法能分析该文法所描述的语言

●二义性的概念、能通过画语法树来分析一个文法描述的语言是否具有二义性。

●Chomsky对文法和所对应语言的分类特别是上下文无关文法的定义和正规文法的定义。能判断

一个语言的文法是哪一类文法

此文法所表示的语言是什么？

过程：（1）找出该语言的一些典型的句子（2）分析句子的特点（3）凑规则（4）写文法（5）验证朂后构造的文法是G[S]:S→(S)|ε

构造描述某种子语言比如十进制带符号的整常数、C语言的标识符等的文法。

给出句子(a,(a,a))的最左、最右推导

文法的左递归性和回溯的消除

1. 文法左递归的消除

当一个文法是左递归文法时,采用自上而下分析法会使分析过程进入无穷循环之中文法左递归是指文法中的某个非终结符 A 存在推导 A ?+ Aα ,而自上而下分析法是施行最左推导,即每次替换都是当前句型中的最左非终结符,当试图用非终结符 A 去匹配输入串时,结果使当前呴型的最左非终结符仍然为 A ,也就是说,在没有读进任何输入符号的情况下,又重新要求 A 去进行新的匹配,于是造成无穷循环。所以采用自上而下汾析法进行语法分析需要消除文法的左递归性

对含直接左递归的规则进行等价变换,消除左递归。

(1 )引进一个新的非终结符,把含左递归的规則改写成右递归
设关于非终结符 A 的直接左递归的规则为
其中 α ,β 是任意的符号串,且 β 不以 A开头,对 A 的规则可改写成如下右递归形式:

改写以後的形式和原来形式是等价的。也就是说,从 A 推出的符号串的集合是相同的
一般情况下,设文法中关于 A 的规则为

其中每个 α 都不等于 ε ,而每個 β 都不以 A 开头,消除直接左递归后改写为

消去非终结符 E , T 的直接左递归后,文法 G [ E ]改写为

消去直接左递归后文法 G [ A ]改写为

(2 )采用扩充 BNF 表示法改写含直接左递归的规则。
在扩充的 BNF 表示中,有如下约定:
① 使用花括号{ α }表示符号串 α 的出现可 0 次或多次,即表示 α*

【例 4.5 】对例 4.3 中文法用扩充 BNF 表示法對其进行改写。

《编译原理》期末试题（一）

一、是非题（请在括号内正确的划√，错误的划×）（每个2分共20分）

1．编译程序是对高级语言程序的解释执行。(× )

2．一个有限状态自动機中有且仅有一个唯一的终态。(×)

3．一个算符优先文法可能不存在算符优先函数与之对应(√ )

4．语法分析时必须先消除文法中的左递归。(×)

5．LR分析法在自左至右扫描输入串时就能发现错误但不能准确地指出出错地点。(√)

6．逆波兰表示法表示表达式时无须使用括号(√ )

7．靜态数组的存储空间可以在编译时确定。(×)

8．进行代码优化时应着重考虑循环的代码优化这对提高目标代码的效率将起更大作用。(×) 9．兩个正规集相等的必要条件是他们对应的正规式等价(× )

10．一个语义子程序描述了一个文法所对应的翻译工作。(×)

二、选择题(请在前括号內选择最确切的一项作为答案划一个勾多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____

A．( ) 单词的种别编码B．( ) 单词在符号表中的位置

C．( ) 单词的种别编码和自身值D．( ) 单词自身值

C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等

我要回帖

更多关于 左递归 的文章

 

随机推荐