編譯器設計中的運算子優先順序解析演算法是什麼？

任何語法字串都可以使用棧實現進行解析，就像在移進規約解析中一樣。但是在運算子優先順序解析中，移進和規約是基於棧頂符號和待解析輸入字串的當前輸入符號之間的優先順序關係來進行的。

運算子優先順序解析演算法如下：

輸入 - 來自某個運算子優先順序語法的優先順序關係和來自該語法的終端符號的輸入字串。

輸出 - 沒有輸出，但它可以在我們解析時構建一個骨架式的語法樹，其中所有內部節點都用一個非終端節點標記，並且沒有顯示單一產生式的使用。或者，可以將移進-規約步驟的序列視為輸出。

方法 - 令輸入字串為 a1a2 … … . an。$最初，棧包含 $。

  • 無限迴圈
  • 如果棧中只有 $ 並且輸入中只有 $ ，則接受並中斷，否則
  • 開始
  • 令 a 為棧上最頂端的終端符號，令 b 為當前輸入符號。
  • 如果 a <. b 或 a =. b ，則將 b 移入棧 /*移進*/
  • 否則如果 a . > b ，則 /*規約*/
  • 重複彈出棧
  • 直到棧頂終端符號與最近彈出的終端符號的關係為 <.
  • 否則呼叫錯誤校正例程 結束。

示例1 - 為語法構建優先順序關係表。

E → E + E|E − E|E ∗ E|E⁄E|E ↑ E|(E)| − E|id

使用假設

運算子優先順序結合性
↑最高右結合
* 和 /次高左結合
+ 和 −最低左結合

解答

運算子優先順序關係


+−*/↑id()$
+.>.><.<.<.<.<..>.>
−.>.><.<.<.<.<..>.>
*.>.>.>.><.<.<..>.>
/.>.>.>.><.<.<..>.>
↑.>.>.>.><.<.<..>.>
id.>.>.>.>.>

.>.>
(<.<.<.<.<.<.<.=
).>.>.>.>.>

.>.>
$<.<.<.<.<.<.<.

示例2 -找出以下語法中各種運算子和符號之間的所有優先順序關係，並使用優先順序表顯示它們。

E → E + T|T

T → T ∗ F|F

F → (E)|id

解答


+*()id$
+.>.<<..><..>
*.>.><..><..>
(<.<.<.=.<.
).>.>
.>
.>
id.>.>
.>
.>
$<.<.<.
<.

更新於： 2021年10月29日

6K+ 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始
廣告