最左派生文法

最左派生文法（Leftmost Derivation）是一種用於描述語言或自動機（如上下文無關文法或上下文無關語言）的生成過程的方法。在文法G中，對於任意句子w，最左派生序列是從文法的開始符號開始，通過不斷套用文法的產生式，每次選擇最左邊的非終結符來替換，直到得到句子w為止。

例如，考慮一個簡單的上下文無關文法G，其開始符號為S，有以下產生式：

S -> aA A -> bB A -> a B -> c

我們可以通過最左派生序列來生成句子"abc"：

1. S -> aA
2. A -> bB
3. B -> c

這個序列從文法的開始符號S開始，每次選擇最左邊的非終結符來替換，直到得到句子"abc"為止。

最左派生文法在理論計算機科學和形式語言理論中有著廣泛的套用，特別是在自動機理論、編譯器和自然語言處理等領域。