最左規約

最左規約（Leftmost derivation）是形式語言理論中的一個概念，用於描述如何從一個開始符號（通常用S表示）通過一系列的規則轉換（或推導）得到一個終端符號序列（通常是一個句子）。在上下文無關文法（Context-free grammar, CFG）中，最左規約是指在應用規則時始終選擇最左邊的非終端符號進行替換的規約過程。

例如，考慮以下CFG：

S -> Aa | b
A -> Ss | ε

其中，S、A是非終端符號，a、b、s是終端符號，ε表示空串。

從開始符號S開始，我們可以進行以下最左規約來得到句子ab:

1. S -> Aa
2. A -> Ss
3. S -> Aa
4. A -> Ss
5. S -> Aa
6. A -> ε

每一步都選擇了最左邊的非終端符號進行替換，直到得到一個只包含終端符號的句子。

最左規約可以用來確定一個句子是否在給定的CFG中，以及如何通過CFG的規則來構造句子。如果一個句子不能通過最左規約來構造，那麼它就不在CFG的語言中。