编译原理:文法转换 发布时间： 2025-03-26 22:35:14 更新时间： 2025-05-09 21:32:08 🕒 阅读时间：3 min read 👀 阅读量：Loading... 文法转换 例 文法GS→aAd∣aBeA→cB→b输入abc 文法G\\ S \rarr aAd | aBe \\ A \rarr c \\ B \rarr b \\ 输入 a b c文法GS→aAd∣aBeA→cB→b输入abc ⚠️同一非终结符的多个候选式存在共同前缀,将导致回溯现象 例 文法GE→E+T∣E−T∣TT→T∗F∣T/F∣FF→(E)∣id输入id+id∗idE⇒E+TE⇒E+T+T... 文法G\\ E \rarr E+T | E - T | T \\ T \rarr T*F | T/F | F \\ F \rarr ( E ) | id \\ 输入 id + id * id\\ E \Rightarrow E + T \\ E \Rightarrow E + T + T \\ ...\\文法GE→E+T∣E−T∣TT→T∗F∣T/F∣FF→(E)∣id输入id+id∗idE⇒E+TE⇒E+T+T... ⛔左递归文法会使递归下降分析器陷入无限循环 概念 💡含有形式产生式的文法称为是直接左递归如果一个文法中有一个非终结符A使得对某个串a存在一个推导,那么这个文法就是左递归的经过两步或两步以上推到产生的左递归成为是间接左递归的 消除直接左递归 A→Aα∣β(a≠ε,β不以A开头)⇓A→βA′A′→αA′∣εA \rarr A\alpha | \beta (a \not= \varepsilon,\beta不以A开头)\\ \Downarrow \\ A \rarr \beta A^{'} \\ A^{'} \rarr \alpha A^{'} |\varepsilonA→Aα∣β(a=ε,β不以A开头)⇓A→βA′A′→αA′∣ε ℹ️事实上,这种消除过程,就是把左递归转换成了右递归 更一般地 A→Aα1∣Aα2∣...∣Aαn∣β1∣β2∣...∣βm(αi≠ε,βj不以A开头)⇓A→β1A′∣β2A′∣...∣βmA′A′→α1A′∣α2A′∣...∣anA′∣εA \rarr A \alpha_1 | A \alpha_2 | ... | A \alpha_n | \beta_1 | \beta_2 | ... | \beta_m \\ (\alpha_i \not= \varepsilon, \beta_j不以A开头 )\\ \Downarrow \\ A \rarr \beta_1 A^{'} | \beta_2 A^{'}|...|\beta_m A^{'} \\ A^{'} \rarr \alpha_1 A^{'} | \alpha_2 A^{'}| ... | a_n A^{'} | \varepsilon A→Aα1∣Aα2∣...∣Aαn∣β1∣β2∣...∣βm(αi=ε,βj不以A开头)⇓A→β1A′∣β2A′∣...∣βmA′A′→α1A′∣α2A′∣...∣anA′∣ε ⚠️消除左递归是要付出代价的---引进了一些非终结符和_产生式 消除间接左递归 例 S→Aα∣bA→Ac∣Sd∣ε>>将S的定义带入A−产生式,得:A−Ac∣Aad∣bd∣ε>>消除A−产生式的直接左递归,得:A→bdA′∣AA′→cA′∣adA′∣εS \rarr A \alpha | b \\ A \rarr Ac | Sd | \varepsilon \\ >>将S的定义带入A-产生式,得:\\ A-Ac | Aad | bd | \varepsilon \\ >> 消除A-产生式的直接左递归,得: \\ A \rarr bdA^{'} | A \\ A^{'} \rarr cA^{'} | adA^{'} | \varepsilonS→Aα∣bA→Ac∣Sd∣ε>>将S的定义带入A−产生式,得:A−Ac∣Aad∣bd∣ε>>消除A−产生式的直接左递归,得:A→bdA′∣AA′→cA′∣adA′∣ε 提取左公因子 例 文法G S→aAd∣aBeA→cB→b⇓S \rarr aAd | aBe \\ A \rarr c \\ B \rarr b \\ \Downarrow \\ S→aAd∣aBeA→cB→b⇓ 文法G′G^{'}G′ S→aS′S′→Ad∣BeA→cB→bS \rarr aS^{'} \\ S^{'} \rarr Ad |Be \\ A \rarr c \\ B \rarr b \\S→aS′S′→Ad∣BeA→cB→b ℹ️通过改写产生式来推迟决定,等读入了足够多的输入,获得足够信息后再做出正确的选择 编译原理:文法转换 作者: xingwangzhe 本文链接: https://xingwangzhe.fun/posts/20304 本文采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。 上一篇 编译原理:NFA转DFA 下一篇 编译原理:LL(1)文法 留言评论评论区内容由用户生成，不代表网站观点
留言评论