算符優(yōu)先文法簡(jiǎn)析和其基于Java的實(shí)現(xiàn)

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

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

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

一、相關(guān)知識(shí)儲(chǔ)備

（一）基本概念

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

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

算符文法

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

算符優(yōu)先文法

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

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

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

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

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

以下文法為例：

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

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

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

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

二、算法實(shí)現(xiàn)

（一）算法思想

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

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

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

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

（二）示例代碼段

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

規(guī)約方法

參考文獻(xiàn)

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

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