精华内容
下载资源
问答
  • 编译原理消除左递归源码 编译原理消除左递归源码 编译原理消除左递归源码 编译原理消除左递归源码
  • 编译原理 消除左递归,直接左递归、间接左递归

    千次阅读 多人点赞 2019-06-24 22:14:45
    消除左递归 左递归的定义 如果存在非终结符PPP经过一步或一步以上推导出PαP\alphaPα,即 P⟹+PαP\stackrel{+}{\Longrightarrow}P\alphaP⟹+​Pα则称PPP含有左递归。 含有左递归的文法将使自上而下的分析过程1...

    消除左递归

    左递归的定义

    如果存在非终结符 P P P经过一步或一步以上推导出 P α P\alpha Pα,即
    P ⟹ + P α P\stackrel{+}{\Longrightarrow}P\alpha P+Pα则称 P P P含有左递归。

    • 含有左递归的文法将使自上而下的分析过程1陷入无限循环。

    左递归的消除

    消除直接左递归

    假定关于非终结符 P P P的规则为 P → P α ∣ β P\to P\alpha|\beta PPαβ其中, β \beta β不以 P P P开头。即, P P P所能确定的是以 β \beta β开头、以若干个 α \alpha α结尾的语言。
    那么,可以把 P P P的规则改写为下面的非直接左递归形式:
    P → β P ′ P\to \beta P' PβP P ′ → α P ′ ∣ ε P'\to \alpha P'|\varepsilon PαPε

    • 举个例子:文法

    E → E + T ∣ T E\to E+T|T EE+TT T → T ∗ F ∣ F T\to T*F|F TTFF F → ( E ) ∣ i F\to (E)|i F(E)i 经过消去直接左递归后变成 E → T E ′ E\to TE' ETE E ′ → + T E ′ ∣ ε E'\to +TE'|\varepsilon E+TEε T → F T ′ T\to FT' TFT T ′ → ∗ F T ′ ∣ ε T'\to *FT'|\varepsilon TFTε F → ( E ) ∣ i F\to (E)|i F(E)i

    消除间接左递归

    先将间接左递归变为直接左递归,再按消除直接左递归的方法进行。

    • 举个例子,文法G[A]

    A → B c ∣ d A\to Bc|d ABcd B → a A ∣ A b B\to aA|Ab BaAAb 转换为直接左递归(代入) A → a A c ∣ A b c ∣ d A\to aAc|Abc|d AaAcAbcd 消除直接左递归 A → a A c A ′ ∣ d A ′ A\to aAcA'|dA' AaAcAdA A ′ → b c A ′ ∣ ε A'\to bcA'|\varepsilon AbcAε 简化为 A → ( a A c ∣ d ) A ′ A\to (aAc|d)A' A(aAcd)A A ′ → b c A ′ ∣ ε A'\to bcA'|\varepsilon AbcAε

    消除全部左递归

    前提:该文法不含回路2

    1. 把文法中所有非终结符按任意一种顺序排列成 P 1 , P 2 , P 3 ⋯   , P n P_{1},P_{2},P_{3}\cdots,P_{n} P1,P2,P3,Pn

    2. 对每个非终结符号,用排在它前面的其他非终结符号的产生式表示出来(代入),并消除产生式中的直接左递归。

    3. 化简上一步所得文法,即去掉重复、多余的产生式。

    • 举个例子,文法G[S]

    S → Q c ∣ c S\to Qc|c SQcc Q → R b ∣ b Q\to Rb|b QRbb R → S a ∣ a R\to Sa|a RSaa 1. 对非终结符排序:R,Q,S
    2. 逐个消除直接左递归: R : R → S a ∣ a R:R\to Sa|a R:RSaa 无直接左递归,将 R R R代入 Q Q Q Q → S a b ∣ a b ∣ b Q\to Sab|ab|b QSababb 无直接左递归,将 R R R Q Q Q代入 S S S S → S a b c ∣ a b c ∣ b c ∣ c S\to Sabc|abc|bc|c SSabcabcbcc 消除 S S S的直接左递归: S → ( a b c ∣ b c ∣ c ) S ′ S\to(abc|bc|c)S' S(abcbcc)S S ′ → a b c S ′ ∣ ε S'\to abcS'|\varepsilon SabcSε 现文法为: S → ( a b c ∣ b c ∣ c ) S ′ S\to (abc|bc|c)S' S(abcbcc)S S ′ → a b c S ′ ∣ ε S'\to abcS'|\varepsilon SabcSε Q → S a b ∣ a b ∣ b Q\to Sab|ab|b QSababb R → S a ∣ a R\to Sa|a RSaa 3. 去掉多余产生式 S → ( a b c ∣ b c ∣ c ) S ′ S\to (abc|bc|c)S' S(abcbcc)S S ′ → a b c S ′ ∣ ε S'\to abcS'|\varepsilon SabcSε

    注意:对非终结符的排序是任意的(但要保证其识别的符号不变),不同的排序最后所得文法的形式可能不同,但他们是等价的。


    1. 自上而下就是从文法的开始符号出发,向下推导,推出句子。 ↩︎

    2. 形如 P → P P\to P PP的推导,也不含有以 ε \varepsilon ε为右部的产生式。 ↩︎

    展开全文
  • 《消除左递归-编译原理实验》由会员分享,可在线阅读,更多相关《消除左递归-编译原理实验(28页珍藏版)》请在人人文库网上搜索。1、编译原理实验报告实验名称:消除左递归______________实验时间:2015-05-27_______...

    《消除左递归-编译原理实验》由会员分享,可在线阅读,更多相关《消除左递归-编译原理实验(28页珍藏版)》请在人人文库网上搜索。

    1、编译原理实验报告实验名称:消除左递归______________实验时间:2015-05-27________________院 系:管理信息工程学院______________班 级:12级计算机科学技术____________学 号:2___________________姓 名:王博一__________________1、 实验目的:理解LL(1)文法中消除左递归的原理2、 实验原理:1直接左递归的消除消除产生式中的直接左递归是比较容易的。例如假设非终结符P的规则为:PP / 其中,是不以P开头的符号串。那么,我们可以把P的规则改写为如下的非直接左递归形式: PP PP / 这两条规则。

    2、和原来的规则是等价的,即两种形式从P推出的符号串是相同的。设有简单表达式文法GE:EE+T/ TTT*F/ FF(E)/ I经消除直接左递归后得到如下文法:ETEE +TE/ TFTT *FT/ F(E)/ I考虑更一般的情况,假定关于非终结符P的规则为PP1 / P2 / Pn / 1 / 2 /m其中,i(I1,2,n)都不为,而每个j(j1,2,m)都不以P开头,将上述规则改写为如下形式即可消除P的直接左递归:P1 P / 2 P /m PP 1P / 2 P / n P /2间接左递归的消除直接左递归见诸于表面,利用以上的方法可以很容易将其消除,即把直接左递归改写成直接右递归。然而文法。

    3、表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归,但却隐藏着左递归。例如,设有文法GS:SQc/ cQRb/ bRSa/ a虽不具有左递归,但S、Q、R都是左递归的,因为经过若干次推导有SQcRbcSabcQRbSabQcabRSaQcaRbca就显现出其左递归性了,这就是间接左递归文法。消除间接左递归的方法是,把间接左递归文法改写为直接左递归文法,然后用消除直接左递归的方法改写文法。如果一个文法不含有回路,即形如PP的推导,也不含有以为右部的产生式,那么就可以采用下述算法消除文法的所有左递归。消除左递归算法:(1) 把文法G的所有非终结符按任一顺序排列,例如。

    4、,A1,A2,An。(2) for (i1;i#include#define N 20char PNN; /规则集char QN; /规则集,存放间接左递归消除后的部分规则char RNN; /用来存放规则的初始值int r; /实际输入的规则的个数int direct(char PNN); /直接左递归函数int indirect(char PNN); /间接左递归函数void directRemove(char PNN); /消除直接左递归函数void indirectRemove(char PNN); /消除间接左递归函数int direct(char PNN) /定义直接左递归函数in。

    5、t flag=0;for(int i=0;i0)printf(经判断该文法含有直接左递归!n);return 1; /属于直接接左递归else return 0; /不属于直接左递归int indirect(char PNN) /定义间接左递归函数int flag=0; for(int i=0;i0)break;if(flag0) printf(经判断该文法含有间接左递归!n);return 2; /属于间接左递归else return 0; /不属于间接左递归void directRemove(char PNN) /定义消除直接左递归的函数int j=4;for(int i=0;i1) co。

    6、py+; /如果有相同左部则规则总数加一for(i=0;i=4;s-)Pi+ks+t-1=Pi+ks;for(int u=3;u=4;s-)Pcopy-1s+t-1=Pcopy-1s;for(int u=3;u连接,规则间用空格隔开);printf(n);for(int k=0;kr;k+)scanf(%s,Pk); printf(n);printf(即输入的文法规则为:n);for(k=0;kr;k+)printf(%sn,Pk);if(direct(P)=1)directRemove(P);else if(indirect(P)=2)indirectRemove(P);elseprintf(经判断该文法不含有左递归!n);实验效果图:消除文法直接左递归实例见下页:消除文法直接左递归实例如下:消除文法间接左递归实例1如下:消除文法间接左递归实例2如下。

    展开全文
  • 编译原理 消除左递归

    万次阅读 多人点赞 2014-02-25 17:46:03
    一个文法含有下列形式的产生式之一时: 1)A→Aβ,A∈VN,β∈V* 2)A→Bβ,B→Aα,A、B∈VN,α、β∈V* 则称该文法是左递归的。...左递归分为直接左递归和间接左递归。 直接左递归经过一次推导就可以看出文法存

    一个文法含有下列形式的产生式之一时:

    1)AAβ,AVN,β∈V*

    2)ABβ,BAα,ABVN,α、β∈V*

    则称该文法是左递归的。

    一个文法G,若存在P经过一次或多次推导得到Pa(即能推导出以P开头的式子), 则称G是左递归的。


    然而,一个文法是左递归时,不能采取自顶向下分析法。

     

    左递归分为直接左递归和间接左递归。

    直接左递归经过一次推导就可以看出文法存在左递归,如PPab

    间接左递归侧需多次推导才可以看出文法存在左递归,如文法:SQccQRbbRSaaS =>Qc =>Rbc =>Sabc

     

    消除左递归方法有:

    a)把直接左递归改写为右递归:

    设有文法产生式:AAβ|γ。其中β非空,γ不以A打头。

    可写为:A→γA'

    A'→βA'|ε

    一般情况下,假定关于A的产生式是:

    AAα1| Aα2 |… |Aαm|β1|β2 ||βn

    其中,αi(1im)均不为空,βj(1jn)均不以A打头。

    则消除直接左递归后改写为:

    A→ β1A'| β2 A' |βnA'

    A'→ α1A' | α2A' |αmA' |ε

     

    例:有文法G(E)

    EE +T |T

    TT*F | F

    F (E)|i

    消除该文法的直接左递归。

    解:按转换规则,可得:

    ETE'

    E'+TE'|ε

    TFT '

    T'*FT'|ε

    F(E)|i


    b)消除间接左递归:

    对于间接左递归的消除需要先将间接左递归变为直接左递归,然后再按a)清除左递归。

    例:以文法G6为例消除左递归:

    (1)AaB

    (2)ABb

    (3)BAc

    (4)Bd

    解:用产生式(1)(2)的右部代替产生式(3)中的非终结A得到左部为B的产生式:

    (1)BaBc

    (2)BBbc

    (3)Bd

    消除左递归后得到:

    BaBcB' |dB'

    B'bcB' |ε

    再把原来其余的产生式AaB,ABb加入,最终得到等价文法为:

    (1) AaB

    (2) ABb

    (3) B(aBc|d)B'

    (4) B'bcB'|ε

     

    c)消除文法中一切左递归的算法

    要求文法不存在经过一次或多次能推导出A和不存在ε产生式(形如A→ε)。 

      1、以某种顺序排列非终结符A1A2,……,An

      2for i = 1 to n do

        {for j = 1 to i - l do

         用产生式Aia1ba2b|……|akb代替每个开如AiAjb的产生式,其中,Aja1a2|……|ak是所有的当前Aj产生式;}

        消除关于Ai产生式中的直接左递归性}

       }

      3、化简由步骤2所得到的文法。

     

      例2:有文法SQcc

    QRbb

    RSaa

    消除文法的左递归。

      以非终结符号排序为RQS

      把R的产生式代入Q中有:

      → (Saabb

      → Sa babb

      把Q的产生式代入S中有:

      → (Sa babbc  

      → Sa bcabcbcc

      消除直接左递归得到结果:

      → abcS’|bc S’|cS’ 

      S’→ abcS’|ε

      → Sa bab

      → Sa

      和 R的产生式是多余的删除,得到最终结果:

      → abcS’|bc S’|cS’ 

            S’→ abcS’|ε

    注意,由于对非终结符排序的不同,最后所得的文法在形式上可能不一样。但不难证明,它们都是等价的。

    例如对上述文法的非终结符排序选为S,Q,R,那么,所得的无左递归文法是:

    把Q的产生式代入S中有:

    S->Qc|c

    S->(Rb|b)c|c

    S->Rbc|bc|c

    把S的产生式代入R中有:

    R->Sa|a

    R->(Rbc|bc|c)a|a

    R->Rbca|bca|ca|a

     消除直接左递归得到结果:

    R->bcaR'|caR'|aR'

    R'->bcaR'|ε

    与上面文法是等价的。

    展开全文
  • 左递归定义 对于一文法,存在非终结符A,A→ Aα,则含有左递归左递归的分类 直接左递归:A → Aa 简介左递归:A → Ba, B → …… → Ab 左递归的消除 直接左递归的消除 形式:A → Aa|b 改写为:A → bA’ ,A...

    左递归定义

    对于一文法,存在非终结符A,A→ Aα,则含有左递归。

    左递归的分类

    直接左递归:A → Aa
    简介左递归:A → Ba, B → …… → Ab

    左递归的消除(构造等价的 LL(1) 文法)

    直接左递归的消除

    形式:A → Aa|b
    改写为:A → bA ,A→ aA

    间接左递归的消除

    例题(消除左递归)

    在这里插入图片描述
    S → (T) ,S → a,S → ε,T → ST,T → ,ST

    展开全文
  • 编译原理课程实验-递归下降分析子程序: 实验目的:掌握最基本的自顶向下分析方法,即递归下降子程序方法,理解其特点和适用范围(回溯,左递归等现象),锻炼递归调用程序的构造方法。 实现功能:给定表达式文法G...
  • 关于消除左递归的文法及代码
  • 编译原理-左递归文法

    千次阅读 2014-09-12 10:56:51
    一个文法G,若存在P经过一次或多次推导得到Pa(即能推导出以P开头的式子), 则称G是左递归的。  左递归分为直接左递归和间接左递归。  直接左递归经过一次推导就可以看出文法存在左递归,如P→Pa|b。  ...
  • 编译原理-递归下降分析器

    万次阅读 2017-12-08 00:10:18
    编译原理-简单的递归下降语法分析器LL(1)在网上看了很多篇关于递归下降分析器的博文,均没有满意的,一是所写的程序不对、二是解释的不够清楚。所以想自己写一篇,顺便总结一下所学。递归下降分析法递归下降分析法的...
  • 编译原理-消除左递归

    千次阅读 多人点赞 2018-05-04 14:53:30
    在进行语法分析的时候,如果采用自上而下的分析方法(从开始符开始,推句子),那么要求文法不是左递归的,进而如果是左递归的,则要求消除左递归 左递归的定义:文法经过一次或多次推导之后,出现如下形式 左递归...
  • 编译原理】文法左递归的消除

    千次阅读 2020-06-30 11:23:24
    文法左递归消除.
  • 编译原理:消除左递归

    千次阅读 2019-06-19 11:08:31
    编译原理:消除左递归 转自:http://guanjy0129.blog.163.com/blog/static/111549445201061491810507/ 时间:2010-07-14 21:18:10 一个文法含有下列形式的产生式之一时: 1) A→Aβ,A∈VN,β∈V* 2) A→B...
  • 编译原理:直接左递归和间接左递归的消除

    千次阅读 多人点赞 2019-06-22 00:25:37
    1.直接左递归的消除 采用扩充BNF表示 设有产生式 A→Aα |Aα |…|Aα |β |β |…|β 设有产生式 A→Aα|Aα|…|Aα|β|β|…|β 引进新的非终结符号,将左递归改写为右递归。 设有产生式 A→Aα |Aα |…|Aα |...
  • 编译原理实验,C/C++实现递归下降分析法的语法分析器
  • 编译原理递归下降分析子程序

    千次阅读 2019-12-10 00:13:35
    掌握最基本的自顶向下分析方法,即递归下降子程序方法,理解其特点和适用范围(回溯,左递归等现象),锻炼递归调用程序的构造方法。 二、实验内容 给定CP语言中简单算术表达式文法G[E]: E→TE’ E’→ATE’|ε ...
  • 编译原理—消除直接左递归

    千次阅读 2018-06-26 15:12:56
    自顶向下语法分析要求无左递归,有左递归会陷入无穷递归。左递归一个文法G,若存在P经过一次或多次推导得到Pa(即能推导出以P开头的式子), 则称G是左递归的。左递归分为直接左递归和间接左递归。直接左递归经过一...
  • 消除左递归消除左递归消除左递归消除左递归消除左递归
  • 在进行语法分析的时候,... 左递归的定义:文法经过一次或多次推导之后,出现如下形式,原理是很简单了。 左递归的分类 直接左递归:P → Pa 简介左递归:P → Aa, A → …… → Pb 直接左递...
  • 消除文法左递归-编译原理

    千次阅读 2017-01-01 17:30:17
    消除文法左递归-编译原理
  • 如有错误欢迎指出,本文章仅是博主个人理解
  • [编译原理] 递归下降语法分析文档_java模拟 产生最推导
  • 编译原理-消除左递归的方法
  • 消除左递归 快速消除左递归 原文法(保证β\betaβ不含PPP):P→Pα1∣Pα2∣Pα3∣...∣Pαn∣β1∣β2∣β3∣...∣βnP \rightarrow P\alpha_1|P\alpha_2|P\alpha_3|...|P\alpha_n|\beta_1|\beta_2|\beta_3|...|\...
  • 使用MFC实现编译原理LL1语法分析器(含消除左递归)使用MFC实现编译原理LL1语法分析器(含消除左递归
  • 编译原理之消除算术表达式文法的左递归
  • 1、递归 (1)递归产生式: ...(2)直接左递归产生式 在递归产生式的基础上,若x = ε\varepsilonε,有 A->Ay 这个称为直接递归产生式 (3)直接右递归产生式 2、消除直接左递归 3、消除间接左递归 ...
  • c代码消除文法左递归_编译原理上机实验全过程
  • #include<bits/stdc++.h> using namespace std; struct GRAM //定义一个产生式结构体 { string left; //定义产生式的左部 string right; //定义产生式的右部 ... char str[80]...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,781
精华内容 9,912
关键字:

编译原理左递归