编译原理:文法转换
00👀 阅读量：Loading...
文法转换
- 例
文法G\\S \rarr aAd | aBe \\A \rarr c \\B \rarr b \\输入 a b c:::warning 同一非终结符的多个候选式存在共同前缀,将导致回溯现象 :::
- 例
文法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 \\...\\:::danger
左递归文法会使递归下降分析器陷入无限循环
:::
概念
:::tip
含有A \rarr Aa形式产生式的文法称为是直接左递归
如果一个文法中有一个非终结符A使得对某个串a存在一个推导A \Rightarrow {}^{+}Aa,那么这个文法就是左递归的
经过两步或两步以上推到产生的左递归成为是间接左递归的
:::
消除直接左递归
A \rarr A\alpha | \beta (a \not= \varepsilon,\beta不以A开头)\\\Downarrow \\A \rarr \beta A^{'} \\A^{'} \rarr \alpha A^{'} |\varepsilon:::info
事实上,这种消除过程,就是把左递归转换成了右递归
:::
更一般地
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:::warning
消除左递归是要付出代价的—引进了一些非终结符和\varepsilon _产生式
:::
消除间接左递归
例
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^{'} | \varepsilon提取左公因子
例
文法G
S \rarr aAd | aBe \\A \rarr c \\B \rarr b \\\Downarrow \\文法G^{'}
S \rarr aS^{'} \\S^{'} \rarr Ad |Be \\A \rarr c \\B \rarr b \\:::info
通过改写产生式来推迟决定,等读入了足够多的输入,获得足够信息后再做出正确的选择
:::
编译原理:文法转换
作者：xingwangzhe
本文链接：https://xingwangzhe.fun/posts/20304/
本文采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
留言评论