在理論計算機科學（TOC）中解釋運算子文法和優先順序分析器

如果文法滿足以下兩個條件，則我們可以說這種型別的文法稱為運算子優先順序文法。

• 如果 ε 在其右部，則不存在任何產生式規則。

• 如果兩個非終結符在其右部彼此相鄰，則不存在任何產生式規則。

運算子文法具有以下屬性：任何產生式的右部都不為空，也不包含兩個相鄰的非終結符。

示例

E-> E A E | id

A-> + | *

上述文法不是運算子文法，但我們可以將其轉換為運算子文法，例如 -

E-> E + E | E * E | id

有三種優先順序關係，如下所示 -

優先順序表

優先順序表

示例

輸入字串如下所示 -

id1 + id2 * id3

插入優先順序關係後為 -

$ <· id1 ·> + <· id2 ·> * <· id3 ·> $

基本原理

• 從左到右掃描字串，直到看到 ·> 並放置一個指標。

• 從右到左反向掃描字串，直到看到 <·。

• 這兩個關係 <· 和 ·> 之間的所有內容構成控制代碼。

• 用產生式的頭部替換控制代碼。

運算子優先順序分析演算法

該演算法如下所示 -

初始化：將 P 設定為指向輸入字串 w$ 的第一個符號。

重複 - 令 b 為棧頂符號，a 為 P 指向的輸入符號。

如果 (a 為 $ 且 b 為 $)

返回

否則

如果 a ·> b 或 a =· b，則

將 a 推入棧

將 P 前進到下一個輸入符號

否則如果 a <· b，則

重複

c -> 彈出棧

直到 (c .> 棧頂)

否則錯誤

結束

示例

使用該演算法構建一個圖。該圖如下所示 -

透過觀察它，我們可以提取優先順序函式，例如 -

Bhanu Priya

更新於： 2021年6月15日

2K+ 瀏覽量

開啟您的 職業生涯

透過完成課程獲得認證

開始學習