什麼是控制代碼？

控制代碼是一個子字串，它連線語法中產生式規則的右側，並且將其歸約到該語法規則左側的非終結符是沿著最右推導的反向的一步。

在每一步中查詢控制代碼

控制代碼可以透過以下過程找到：

• 它可以從左到右掃描輸入字串，直到遇到第一個 .>。

• 它可以向後掃描，直到遇到 <.

• 控制代碼是 <. 和 .> 之間的字串。

示例1 - 考慮語法

E → E + E|E * E|(E)id。

使用運算子優先順序解析，在每一步中查詢歸約字串 id₁ + id₂ * id₃ 的控制代碼。

解決方案

首先，在字串的開頭和結尾附加 $，即 $id₁ + id₂ * id₃ $。

使用優先順序關係表在運算子和符號之間放置優先順序關係。

∴ $ <. id₁. > +<. id₂ >*<. id₃ > $

對字串應用上述 3 個步驟。

示例2 - 計算以下語法中非終結符 E、T 和 F 的 FIRST 和 LAST 終結符。

E → E + T| T

T → T * F | F

F → (E)| id

解決方案

檢視產生式，我們可以判斷

+ 是 E 的第一個終結符

* 是 T 的第一個終結符

(, id 是 F 的第一個終結符。

但是 E → T → F

∴ F 的第一個終結符包含在 T 的第一個終結符中，T 的第一個終結符包含在 E 的第一個終結符中。

∴ First(F) = {(, id}

∴ First(T) =*∪ First (F) = {*, (, id}

First(E) = + ∪ First (T) = {+,*, (, id}

同樣，可以找到 Last 終結符。

示例3 - 考慮語法

E → E + T|T

T → T ∗ F|F

F → (E)| id

使用運算子優先順序解析對字串 id + id * id 執行棧實現。

解決方案

棧頂和當前輸入符號之間存在優先順序規則 <. , .> 或 =. 。如果棧頂是非終結符，則將棧頂下方的終結符與當前輸入符號進行比較。

Ginni

更新於： 2021-10-29

9K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習