编译原理问题（一）
编译原理问题（一）
- 单词识别
单词识别
- 单词识别：识别整数和浮点数
#
现有一文法如下
( 1 ) E → E + E ( 2 ) E → E ∗ E ( 3 ) E → ( E ) ( 4 ) E → i (1)E \rightarrow E + E \\ (2)E \rightarrow E * E \\ (3)E \rightarrow ( E ) \\ (4)E \rightarrow i (1)E→E+E(2)E→E∗E(3)E→(E)(4)E→i
消除二义性：（添加优先级）
( 1 ) E → E + T ∣ T ( 2 ) T → T ∗ F ∣ F ( 3 ) F → ( E ) ∣ i (1) E \rightarrow E+T\ | \quad T \\ (2) T \rightarrow T*F \ | \quad F \\ (3) F \rightarrow (E) \ | \quad i (1)E→E+T ∣T(2)T→T∗F ∣F(3)F→(E) ∣i
消除左递归：
方法:有 P → P α ∣ β P \rightarrow Pα|β P→Pα∣β的产生式将其替换为形式等价的产生式组：
( 1 ) P → β P ′ ( 2 ) P ′ → α P ′ ｜ ε (1)P\rightarrow βP’ \\ (2) P’ \rightarrow αP’ ｜\varepsilon (1)P→βP′(2)P′→αP′｜ε
一般而言，若产生式形式为：
A → A α 1 ∣ A α 2 ∣ … ∣ A α n ∣ β 1 ∣ β 2 ∣ … ∣ β m A→Aα_1|Aα_2|…|Aα_n|β_1|β_2|…|β_m A→Aα1∣Aα2∣…∣Aαn∣β1∣β2∣…∣βm
将其替换为：
( 1 ) A → β 1 B ∣ β 2 B ∣ … ∣ β m B （ 2 ) B → α 1 B ∣ α 2 B ∣ … ∣ α n B ∣ ε (1)A \rightarrow β_1 B|β_2 B |…|β_m B \\ （2)B \rightarrow α_1 B|α_2 B |…|α_n B|ε (1)A→β1B∣β2B∣…∣βmB（2)B→α1B∣α2B∣…∣αnB∣ε
将上式消除左递归如下：
( 1 ) E → T E ′ ( 2 ) E ′ → + T E ′ ∣ ε ( 3 ) T → F T ′ ( 4 ) T ′ → ∗ F T ′ ∣ ε ( 5 ) F → ( E ) ∣ i (1)E \rightarrow TE’ \\ (2)E’ \rightarrow +TE’ | \ \varepsilon \\ (3)T \rightarrow FT’ \\ (4)T’ \rightarrow *FT’ \ | \ \varepsilon \\ (5)F \rightarrow (E) \ | \ i (1)E→TE′(2)E′→+TE′∣ ε(3)T→FT′(4)T′→∗FT′ ∣ ε(5)F→(E) ∣ i
消除回溯:
A → δ α 1 ∣ δ α 2 ∣ … ∣ δ α n A→δα1|δα2|…|δαn A→δα1∣δα2∣…∣δαn 转换成:
( 1 ) A → δ A ′ ( 2 ) A ′ → α 1 ∣ α 2 ∣ … ∣ α n (1)A\rightarrowδA’ \\ (2) A’ \rightarrowα1|α2|…|αn (1)A→δA′(2)A′→α1∣α2∣…∣αn
上式的文法产生式：
向右看齐
梦里梦外;
不念不忘少年蓝@
野性酷女
还没有评论，来说两句吧...