剖析／語法分析（parsing）

想像你讀一個句子，不只是檢查它合不合文法，而是真的畫出老師教你的句法圖：這是主詞、那是動詞、這個子句掛在那個名詞底下。剖析就是這件事的電腦版本。給定一串符號和一套說明何者合法的文法，剖析同時回答兩個問題。第一，這個字串屬於該文法所產生的語言嗎？第二，同樣重要的是，它的結構是什麼：用了哪些規則、以怎樣的巢狀方式把它建出來？

具體而言，剖析器接受一個上下文無關文法（context-free grammar, CFG）和一個輸入字串，試圖找出一個推導：一連串把文法的起始符號變成恰好那個字串的規則套用。輸出通常是一棵剖析樹（parse tree），其根是起始符號，葉子由左到右拼出輸入，內部節點則是所用的文法規則。對文法 E -> E + E | num 與輸入 2 + 3，剖析器必須發現整體是一個 E，由兩個較小的 E 以加號連接而成。光是判定成員是容易的那一半；把樹還原出來，好讓後續階段知道 2 與 3 是那個加號的運算元，才是讓剖析成為編譯器主力的部分。

剖析之所以重要，是因為電腦讀進來的幾乎所有東西都是必須被理解、而不只是被掃描的結構化文字：程式原始碼、JSON 與 XML、設定檔、查詢語言，甚至網路協定訊息。上下文無關文法的理論告訴我們哪些結構可以被描述；剖析則是把那些文法變成真能讀出結構的程式的工程。它是形式語言理論最看得見的回報。