编译原理问题（一）

梦里梦外; 2023-08-17 16:04 114阅读 0赞

### 编译原理问题（一） ###

*   *  单词识别
     *

## 单词识别 ##

*  单词识别：识别整数和浮点数  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]

##  ##

现有一文法如下  
 ( 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

上式的文法产生式：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]: /images/20230810/096c8f875fc8478696a3be93e370211c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 1]: /images/20230810/8d87f9cf1b1a4a1bada75d9ebe61d4b9.png