摘 要：算符優(yōu)先文法并不是一種規(guī)范的規(guī)約，但是它文法結(jié)構(gòu)簡單，易于實現(xiàn);其終結(jié)符之間按照規(guī)約的先后關(guān)系排列優(yōu)先級，這一特點很有利于初學(xué)者對于從下到上的語法分析思想的理解。

本文首先介紹算符優(yōu)先分析相關(guān)的基本概念，包括優(yōu)先關(guān)系表;之后將給出使用Java語言實現(xiàn)這一語法分析方法的示例代碼段。

關(guān)鍵詞：編譯原理;從下到上分析方法;算符優(yōu)先分析;優(yōu)先關(guān)系表

一、相關(guān)知識儲備

（一）基本概念

優(yōu)先關(guān)系

最基本的優(yōu)先關(guān)系是四則運算中的算符優(yōu)先關(guān)系，乘號的優(yōu)先級大于加和減;左括號的優(yōu)先級大于乘號，等等。算符優(yōu)先分析中的優(yōu)先級關(guān)系并不是一成不變的，而是對位置敏感的。同樣是加號和乘號，表達式中，加號出現(xiàn)在乘號的左邊和右邊的優(yōu)先級可能會不同;而且，根據(jù)語法樹中規(guī)約的先后順序，在同一個表達式中，如果句型的規(guī)約順序發(fā)生變化，相同位置關(guān)系下的兩個終結(jié)符的優(yōu)先關(guān)系也會變化?；镜乃惴麅?yōu)先關(guān)系有三種：優(yōu)先關(guān)系等于、小于、大于。

算符文法

算符文法規(guī)定，文法的任何一個產(chǎn)生式的右部都不含兩個相繼（并列）的非終結(jié)符，也就是說每兩個非終結(jié)符之間必含有至少一個終結(jié)符。這一規(guī)定是算符優(yōu)先分析的精妙之處，極大地簡化了文法的實現(xiàn)難度。

算符優(yōu)先文法

成為算符優(yōu)先文法有四個條件：

1.是算符文法;2.不含有ε產(chǎn)生式;3.對于任何一對終結(jié)符都有三種優(yōu)先關(guān)系之一;

4.任何一對終結(jié)符最多只滿足三種優(yōu)先關(guān)系之一。

（二）優(yōu)先關(guān)系表

優(yōu)先關(guān)系表是使用代碼實現(xiàn)算符優(yōu)先分析的關(guān)鍵，該表使得終結(jié)符之間的優(yōu)先關(guān)系得以存放在一個二維數(shù)組中。制作優(yōu)先關(guān)系表之前，首先要做出每個非終結(jié)符的FIRST-VT集和LAST-VT集合。這兩個集合都是根據(jù)文法的產(chǎn)生式得出的，具體得出方式在此不再詳述。VT代表的是終結(jié)符，F(xiàn)IRST-VT指的是在各個非終結(jié)符的產(chǎn)生式中首次出現(xiàn)的終結(jié)符;相對應(yīng)的，LAST-VT是指各個非終結(jié)符的產(chǎn)生式中最后出現(xiàn)的終結(jié)符。有了這兩個集合之后，就對此時空白的優(yōu)先關(guān)系表按行和按列填滿。（以下內(nèi)容中的小寫字母代表終結(jié)符，大寫字母代表非終結(jié)符）。

以下文法為例：

對于形如...aP...的產(chǎn)生式，是出現(xiàn)在左邊的a和P的FIRSTVT（P）集作比較（a

對于形如...Pa...的產(chǎn)生式，是出現(xiàn)在右邊的a和LASTVT（P）作比較（LASTVT（P）>a），此時要關(guān)注終結(jié)符a占據(jù)的列，是對優(yōu)先關(guān)系表按列填滿。

需要注意的是，不管是按行填滿還是按列填滿，表格中的優(yōu)先關(guān)系大小永遠表示的是該格所在行的終結(jié)符和該格所在列的終結(jié)符的優(yōu)先關(guān)系。

最終示例優(yōu)先關(guān)系表為：

二、算法實現(xiàn)

（一）算法思想

算符優(yōu)先分析終究是一種自下而上的規(guī)約方法。在代碼實現(xiàn)時，關(guān)鍵是使輸入串和分析棧中的字符不斷地進行優(yōu)先級的比較。分析棧存放的是從輸入串中讀入的字符和規(guī)約的結(jié)果。大致過程是：

1.當(dāng)分析棧中的字符優(yōu)先級比輸入串當(dāng)前待輸入的字符低或等于時，入棧一個字符;

2.重復(fù)執(zhí)行1，直至分析棧棧頂?shù)慕K結(jié)符優(yōu)先級比棧外輸入串的首字符高;此時由棧頂向下尋找并讀取經(jīng)過的字符，直到讀到的字符的優(yōu)先級比棧頂元素低，那么這時，從棧頂?shù)皆撟址暗淖址?，這一串就被稱為“最左素短語”（含有且僅有一個終結(jié)符），是可以被規(guī)約的字符串，將這一串字符出棧，將規(guī)約的結(jié)果進棧;

3.重復(fù)步驟1和2，直至輸入串所有字符處理完畢。

（二）示例代碼段

尋找可規(guī)約串與移進字符

規(guī)約方法

參考文獻

[1] 陳火旺，等.程序設(shè)計語言編譯原理（第3版）[M].北京：國防工業(yè)出版社，2006： 89-98

作者簡介：劉楊（1999——）男，漢族，河南信陽人，單位：河南大學(xué)計算機與信息工程學(xué)院，本科，軟件工程專業(yè)，軟件工程：