3.3文法分析-分析樹與二義性

前端

• 源程式–<詞法分析器–記号–文法分析–抽象文法樹–語義分析器>–中間表示

文法分析器的任務

• 記号流和語言的文法規則–>文法分析器–>文法樹

推導與分析樹

S -> N V N  (名詞 動詞 名詞)
N -> s      // 羊
   | t      // 老虎
   | g      // 草
   | w      // 水
V -> e      // 吃
   | d      // 喝
           

• 在推導的過程中有多條路可以走，不同的路可能導緻不同的結果
• 如果選錯路徑就要回溯重新走另一條路徑，如果走完所有路徑都還沒有比對到那就報錯，如果中間有比對到，就算文法正确

分析樹

• 推導可以表達成樹狀結構
  • 和推導所用的順序無關（最左、最右、其他）
• 特點：
  • 樹中的每個内部節點代表非終結符
  • 每個葉節點代表終結符
  • 每一步推導代表如何從雙親節點生成它的直接孩子節點

表達式的例子

E -> num
   | id
   | E + E
   | E * E
           

• 推導：3+4*5
  • 左推導

E -> E + E
  ->  + E
  ->  + E * E
  ->  +  * E
  ->  +  * 
           

• 右推導

E -> E * E
  -> E + E * E
  ->  + E * E
  ->  +  * E
  ->  +  * 
           

• 根據左右推導的結果可以看出，同樣的文法推導出來的結果有所不同，其中涉及優先級問題

二義性文法

• 給定文法G，如果存在句子S,它有兩棵不同的分析樹，那麼稱G是二義性文法
• 從編譯器角度，二義性文法存在問題：
  • 同一個程式會有不同的含義
  • 是以程式運作的結果不是唯一的
• 解決方案：文法的重寫

表達式文法的重寫

E -> E + T
   | T
T -> T * F
   | F
F -> num
   | id
           

• 推導：3+4*5

E -> E + T
  -> T + T
  -> F + T
  ->  + T
  ->  + T * F
  ->  + F * F
  ->  +  * F
  ->  +  * 
           

• 推導：3+4+5

E -> E + T
  -> E + T + T
  -> T + T + T
  -> F + T + T
  ->  + T + T
  ->  + F + T
  ->  +  + T
  ->  +  + F
  ->  +  +