文法转换

文法GSaAdaBeAcBb输入abc 文法G\\ S \rarr aAd | aBe \\ A \rarr c \\ B \rarr b \\ 输入 a b c


同一非终结符的多个候选式存在共同前缀,将导致回溯现象

文法GEE+TETTTTFT/FFF(E)id输入id+ididEE+TEE+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 \\ ...\\

左递归文法会使递归下降分析器陷入无限循环

概念

💡

含有AAaA \rarr Aa形式产生式的文法称为是直接左递归


如果一个文法中有一个非终结符A使得对某个串a存在一个推导A+AaA \Rightarrow {}^{+}Aa,那么这个文法就是左递归


经过两步或两步以上推到产生的左递归成为是间接左递归

消除直接左递归

AAαβ(aε,β不以A开头)AβAAαAεA \rarr A\alpha | \beta (a \not= \varepsilon,\beta不以A开头)\\ \Downarrow \\ A \rarr \beta A^{'} \\ A^{'} \rarr \alpha A^{'} |\varepsilon

ℹ️

事实上,这种消除过程,就是把左递归转换成了右递归

更一般地

AAα1Aα2...Aαnβ1β2...βm(αiε,βj不以A开头)Aβ1Aβ2A...βmAAα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

消除左递归是要付出代价的—引进了一些非终结符ε\varepsilon _产生式

消除间接左递归

SAαbAAcSdε>>S的定义带入A产生式,:AAcAadbdε>>消除A产生式的直接左递归,:AbdAAAcAadAε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

SaAdaBeAcBbS \rarr aAd | aBe \\ A \rarr c \\ B \rarr b \\ \Downarrow \\

文法GG^{'}

SaSSAdBeAcBbS \rarr aS^{'} \\ S^{'} \rarr Ad |Be \\ A \rarr c \\ B \rarr b \\

ℹ️

通过改写产生式来推迟决定,等读入了足够多的输入,获得足够信息后再做出正确的选择