一霞赫、緒論

編譯程序

• 功能：高級pro轉低級目標pro
• 形式
  • 編譯執(zhí)行
    • 轉obj在執(zhí)行盏混，效率高
    • 跨平臺性差
  • 解釋執(zhí)行
    • 逐行解釋，效率低
    • 跨平臺性好

編譯過程/結構

• 詞动雹、語法、語義...
• 結構：各種分析器+表格跟压、錯誤管理

編譯程序實現(xiàn)

• 自編譯
• 交叉~
• 自展
• 移植

解釋&編譯程序區(qū)別

0胰蝠、不生成obj & 生成~
1、邊解釋邊執(zhí)行 & 轉目標程序再執(zhí)行
2震蒋、速度慢茸塞，效率低 & _快，高
3查剖、跨平臺性好 & ~差
4钾虐、可動態(tài)修改 & 修改不方便

相關細節(jié)

• 編譯過程分模塊是為了使pro結構清晰
• 編譯pro時間大多花在表格管理上

2、詞法分析

功能：

• 輸入源pro笋庄，輸出可識別單詞
• 字符掃描器

分析形式

• 單獨做主pro
• 作語法分析pro的子pro

輸出形式

• 二元式
• （單詞種別,單詞值）

識別單詞形式

• 狀態(tài)轉換圖
  • 識別單詞的有限有向圖
• 狀態(tài)轉換圖組成

1效扫、結點

• 圓圈表示
• 代表狀態(tài)
  • 必有初態(tài)、終態(tài)
  • 每個狀態(tài)對應一小段程序
• 結點數(shù)有限

2直砂、有向邊

• 連接結點
• 邊上標記字符

• 狀態(tài)矩陣：轉換圖的一種實現(xiàn)形式
  1菌仁、行表示狀態(tài)
  2、列表示輸入符
  3哆键、矩陣元素表示f(s,a)值

• 正規(guī)表達式

  • 形式化表示法
    • 表示單詞符號的結構
  • 定義單詞符號集

• 有限自動機

  • 實現(xiàn)狀態(tài)轉移的自動機
  • 一般化的狀態(tài)轉換圖
  • 類別
    • 確定-DFA
    • 非確定-NFA

題型

• 構造簡化DFA
  • 根據(jù)正規(guī)式—>NFA->DFA->簡化DFA
• 比較正規(guī)式是否等價
  • 求兩個正規(guī)式的狀態(tài)轉換矩陣掘托，相等則等價

相關細節(jié)

• DFA/NFA區(qū)別
  • 一個/若干個初始態(tài)
  • 單/多值函數(shù)
    • 即同一狀態(tài)，同一輸入字符籍嘹，對應一/多個輸出狀態(tài)

3闪盔、語法分析

功能

根據(jù)語法規(guī)則弯院，輸出分析樹（短語、句子）

概念

• 文法

  • 1泪掀、proLang的生成系統(tǒng)

  • 2听绳、精確定義一個語言

  • 四元組

    • 終結符集
    • 非終結符集
    • 開始符
      一般為S
    • 產(chǎn)生式的非空有限集
      產(chǎn)生式：語法實體書寫規(guī)則
      S——>Ta

  • 類別

    • 0型文法
      （1）短文法
      （2）α至少有一個非終結符
      （3）例：A—>ab
    • 1型文法
      （1）上下文有關文法
      （2）α->β，且|β|>=|α|
      （3）正例：A->Ba
      （4）例：aA->a
    • 2型文法
      （1）上下文無關文法
      （2）α->β异赫，|β|>=|α|椅挣，且α為非終結符
      （3）正例：AB->abc
      （4）錯例：aB->abc
    • 3型文法
      （1）正規(guī)文法
      （2）2型文法基礎上，滿足左線性或右線性
      （3）左線性：A->a|Ba
      （4）右線性：A->a|aB

  • 四類文法

    • 聯(lián)系
      （1）0到3塔拳，逐漸增加限制
      （2）1到3鼠证，均屬0
      （3）2、3靠抑，不屬1
    • 區(qū)別
      1不許"A->ε, 2量九、3允許

  • 文法二義性

    • 二義性影響pro執(zhí)行
    • 二義性消除
      方法一：加進一些語法的非形式規(guī)定
      如運算符的優(yōu)先規(guī)則
      方法二：構造等價無二義性文法
    • 二義文法
      定義: 文法中某個句子存在一棵以上的語法樹
      無法判定
      無算法

  • 相關細節(jié)

    • 錯誤：文法限制越大，語言越小
    • 3型文法：描述高級pro的詞法
    • 2型文法：描述高級pro的語法
    • NFA/DFA:識別高級pro的的詞法
    • 下推PDA：識別高級pro的語法
    • 正規(guī)文法&表達式
      前：描述颂碧、定義一個語言
      后：識別是否符合某個語言
    • 文法唯一對應一種語言
    • 語言可對應多個文法
• 推導
  • 例：αAβ=>αiβ
  • =>直接推導 & ->產(chǎn)生式定義符號
  • 句型
    • 終結符U非終結符
    • E+E荠列、E+E*i
  • 句子
    • 終結符
    • i+i*i
  • 推導形式
    • 最右推導
    • 最左推導

• 語法樹
  • 定義
    • 圖示化形式分解句子
      各組成部分描述句子語法結構
    • 語法樹與文法相一致
    • 滿足的條件
      （1）結點用終或非終標記
      （2）根結點用S標記
      （3）子結點一定是非終結符
  • 短語
    • 子樹末端節(jié)點形成的符號串
    • 子樹根的短語
  • 直接短語
    • 簡單子樹末端節(jié)點形成的符號串
    • 簡單子樹根的直接短語
  • 句柄
    • 最左簡單子樹的末端節(jié)點形成的符號串
  • 素短語
    • 子樹
    • 有終結符
    • 無更小子樹

形式

（1）自頂向下

• 文法 推 句子
  文法開始符 推 輸入串
• 分析方法

  • 遞歸下降分析法

    • 定義
      A. 根節(jié)點出發(fā)
      B. 自頂向下匹配輸入串
      C. 建立語法樹
    • 自頂向下分析的不確定性

      • 壞處
        A. 窮舉法
        B. 效率低

      • 改進：確定的自頂向下分析
        A. 消除左遞歸

          左遞歸  改  右遞歸
           A->Aa|β
              A->βA'
              A'->αA'|ε
        

        B. 消除回溯
        發(fā)生回溯原因: 存在公共左因子

  • LL(1)分析法

    • 定義

      • 又稱預測分析法
      • 不回溯、非遞歸
      • 1L：自左向右载城；2L：最左推導肌似；(1):向右查看一個符號

    • 核心

      • 構造文法的LL(1)分析表

    • LL(1)文法

      • 無二義
        • 分析表無多重定義入口
        • 途徑：消除左遞歸
      • 無回溯

    • 構造過程
      1、求First集

        X->a...,將a置入First(X)
        X->Y...,First(Y)置入First(X)
        X->Y1Y2Y3..Yk,First(Y1Y2Y3..YI)置入First(X)
      

      2诉瓦、求Follow集

        置#于Follow(S)
        若A->aBT,置Frist(T)-空于Follow(B)
        若Ａ?αB,或Ａ?αBβ,而β=>*e川队，置FOLLOW（A）于FOLLOW（B）中．
      

      3、構造分析表

        出現(xiàn)多重入口睬澡，遵從相應匹配原則（題意會給出）
      

  • 疑問

    • 構造LL(1)分析表的過程即是消除二義性的過程呼寸？
    • 構造過程中，求完First集猴贰，直接畫分析表对雪，對形如"A->ε"進行Follow集，可否米绕？

  • First和Follow集含義

    • First(α)是α的所有可能推導的開頭終結符或可能的ε
    • Follow(A)是所有句型中出現(xiàn)在緊隨A之后的終結符或“#”

（2）自底向上

• 句子 推 文法
  輸入串 推 文法開始符

• 定義

  • 自左向右
  • 循環(huán)查找句柄
  • 歸到開始符號瑟捣，停止

• 過程

  • 移進，形成句柄栅干，就規(guī)約
  • 重復上述過程迈套，遇開始符號，成功
  • PS：規(guī)約的中心問題尋找一個句型的句柄

• 分析方法

  • 算符優(yōu)先文法
    • 特點
      • 簡單直觀
      • 擅分析各類表達式
      • 宜手工實現(xiàn)
    • 關鍵
      • 預先規(guī)定運算法之間的優(yōu)先關系
      • 相繼兩個終結符的優(yōu)先關系
      • 找最左素短語
        • 至少含一個終結符
        • 最小性
          自身不得再含素短語
        • 最左性
    • 定義與構造過程

      • 優(yōu)先關系定義
        a≡b
        A→…ab…或A→…aBb…

        a≮b
        A→…aB…,且B=>b…或B=>Cb…

        a≯b
        A→…Bb…碱鳞，且B…a或B…aC

      • FIRSTVT集構造
        A->b... 或A->Bb...
        b∈FIRSTVT(A)
        A->B…
        FIRSTVT(B)∈FIRSTVT(A)

      • LASTVT集構造
        A->...b 或A->...bB
        b∈LASTVT(A)
        A->…B
        LASTVT(B)∈LASTVT(A)

      • 優(yōu)先關系表構造

        • 改進：構造優(yōu)先函數(shù)
          • 好處
            • 節(jié)省空間
            • 便于比較運算
          • 方法
            • 關系圖法
              若a.>b桑李，fa 至gb畫一條弧
              若a <.b，fa至gb畫一條弧贵白；
              該結點所能到達的所有結點
              包括下級結點所能到達的結點
            • 定義法（Floyd法）

              • 步驟
                1率拒、令f(x) = g(x) = 1
                2、比較

                  x <. y禁荒，如果f(x)≥g(y)猬膨，則令g(y) = f(x) + 1
                  x .> y，如果f(x)≤g(y)呛伴，則令f(x) = g(y) + 1
                  x  =  y勃痴，如果f(x)≠g(y)，則令f(x) = g(y) = max(f(A)
                

                3热康、大于2n沛申，非算符優(yōu)先文法

• 規(guī)范規(guī)約方法（找句柄）

  • LR分析法
    • 定義
      • 1L：自左向右
      • 2R：逆最右推導（規(guī)范規(guī)約）
    • 特點：局限大，基礎
    • 原理
      • 自左向右
      • 循環(huán)查找句柄
        活前綴
      • 歸到開始符號姐军，停止
    • 項目類別
      • 歸約項目: A->α·
      • 移進項目: A->α·aβ
      • 待約項目: A->α·Bβ
      • 接受項目: S’->S ·
    • 構造步驟
      1污它、拓廣
      2、求CLOSURE({S’->·S}),得到初態(tài)項目集
      3庶弃、重復2，知道無新項目
      4德澈、GO函數(shù)構造文法DFA
      5歇攻、生成LR(0)分析表
      PS:生成LR（0）表時，歸約r1梆造，r2..決定于歸約項目所對應的編號
  • SLR(1)分析法
    • 簡單LR表
    • 易實現(xiàn)缴守，有使用價值
    • 過渡
  • LR(1)分析法
    • 規(guī)范LR表
    • 適用大多數(shù)DFG
    • 體積龐大
    • 理論過渡
  • LALR(1)分析法
    • 實用
    • 能力在SLR(1)和LR(1)之間

題型

• 判斷產(chǎn)生式文法類別：例3.3
• 正規(guī)式，求正規(guī)文法：例3.4
  • 畫DFA镇辉，再推正規(guī)文法
• 上下文無關文法描述正規(guī)表達式：例3.5
• 構造LL(1)分析表
• 證明文法是LL(1)文法
• 構造算符優(yōu)先關系表屡穗、優(yōu)先函數(shù)
• 構造LR(0)分析表

相關細節(jié)

• 文法相關定義
  • 大寫字母：非終結符
  • 小寫字母：終結符
  • 希臘字母：文法符號串