Question

求解一段语法分析 学过编译原理的进

我已经对语法分析有了解了，但是下面一些字符含义不是很明
E T F G I是什么意思，’又是什么意思，ε这个是不是可以代表任意符号？

1．算术表达式文法
G(E)： E-> E +T | T
T ->T* F | F
F->i | (E)
2．文法变换：
G’(E)： E->TE'
E'->+TE'|ε
T->FT'
T'->*FT'|ε
F->(E)|I
最近看编译原理不是很明白

seq->seq instr | begin
instr->north | south | west | east

那么语句可以写为begin north east south

语法在哪里规定了一定是begin开头？

Answer 1

E是文法开头。ε代表终结符号(推理中代表终点或结果，程序语言中代表常量等)。E T 这些大写字母一般代表非终结符号（这些代表中间过程，非结果。程序中代表函数等等）。开始是E。因为有个G(E)。E就是文法开始符号。推导就有E开始，它也是一个非终结符(代表函数、或者一个推导过程，类似于程序中的main(c++)、winmain(vc++)、dllmain(dll)等主函数）。

1算术表达式文法：这个文法是一个递归文法。计算机进行逻辑推导时会走很多弯路（类似于遍历一颗树的过程）。为了不让计算机走弯路（提高效率的目的），可以变换为第二种文法。这种文法消除了递归（消除了歧义，类似于后缀表达式），使计算机可以一条直线走到底儿推导出结果。

我也很久没看编译原理了。 呵呵

追问

谢谢 我还想问一下
E-> E +T | T
T'->*FT'|ε
seq->seq instr | begin
这三句是不是递归定义？

还有 F->(E)|I 这句是什么意思？

追答

我说的递归主要是指左递归。为什么是左递归？这可能是一种习惯，也可以消除右递归（但这样仍然不能快速得到终结符，因为这样变换后终结符都跑到后面去了，消除左递归后终结符跑到式子前面，是不是很形象。一眼就能看出如果要得到一个*号，那么必定要用到这样一个式子T'->*FT'。当然这里面还涉及到first、follow集及select集的知识。这些集合都是帮助寻找你需要的终结符用得，目的当然是避免走冤枉路（避免回溯，回溯是很耗时和耗资源滴））。
这种消除左递归的分析方法叫做自上而下的分析方法。（这种方法要求从文法开始符号开始，向下推导，推出句子。而且不能有分歧。所谓歧义指当面临一种选择，A暂时可以，B也暂时可以，确定到底那个能行只有两种情况分别试一下。这种具体结果要未来才能确定时就是有分歧的。）这也是为什么要消除左递归的原因。因为你往A走下去，发下原来A不是正确结果，那么你就必须返回当初选择点，然后走B路。这样就走了弯路。
E->E+T就产生了左递归，因为可以出现这样的推导E->E+T+T或者再递归一次变成E->E+T+T+T。而且你没有一种可预见性。当你进行搜索时只能盲目进行，最坏情况下可能要试遍所有情况才能得到结果（你想要的终结符）。
比如你有T的一个Select集合Select(T->xxx) = {a},那么你就可以预计出如果要得到一个非终结符a，那么一定要用T->xxx这个推导。
T'->*FT'是一个递归，但是它不是一个左递归。对于自上而下的分析方法没问题。

还有T'->*FT'|ε其实是两个式子。一个T'->*FT'还有一个T'->ε。

F->(E)|i表示F可以推导出这样一个式子（E）或i。其中（E）中左右括号都是终结符，E是非终结符。由于E->E+T，那么有T'->（E+T)或T'->(T)。