一个简单的语法分析器(后缀式转换)

编译原理很神奇，经过一次次小小的步骤，然后奇迹就出现了。

对于中缀式转后缀式，这已经不算一个很困难的问题了，之前也学了很多能够解决此问题的数据结构和算法，比如栈和表达式树。今天算是又多学了一种解法。不同的是，该方法更强劲。

构造产生式

定义一下字母表 {0-9+-*/ \t\n}

产生式:

expr	->	expr + term
	|	expr - term
	|	term
term	->	term * factor
	|	term / factor
	|	factor
factor	->	digits | (expr)
digits	->	digits digit | -digits
digit	->	0|1|2|3|4|5|6|7|8|9

 

 

 

 

 

 

 

 

 

 

 

 

可以看到，该生成产生式支持 "()"的嵌套和"-"(负)运算, 例如 12+-3/(21-7+(1)) 是支持的.

该产生式不能处理空白字符, 例如 1 + 2，想要支持这样的语法，只需要在编写程序的时候多一个判断，即如果 向前看(lookahead) 符号为空白符，跳过即可.

 

处理左递归

为了能够顺利的编写程序，要首先处理掉产生式中存在的左递归. 

expr	->	expr + term
	|	expr - term
	|	term

 

 

 

 

对于上面的产生式，我们可以做如下处理

expr	->	term rest
rest	->	+ term rest
	|	- term rest
	|	ε

 

 

 

 

 

 

 

如此便消除了左递归，我们可以将该产生式用另一种方式表示出来

expr

->

term ((+|-) term)*

 

 

注:其中 A^*的意思是 A 可以出现 任意次

 

语义动作

接下来把表达式翻译成后缀形式的语义动作:

expr	->	expr + term	{print ('+')}
	|	expr - term	{print ('-') }
	|	term
term	->	term * factor	{print('*')}
	|	term / factor	{print('/') }
	|	factor
factor	->	digits | (expr)
digits	->	digits digit | -digits	{print(' ')}
digit	->	0|1|2|3|4|5|6|7|8|9	{print(digit)}

 

 

 

 

 

 

 

 

 

 

 

 

编写代码

最后的任务就是编写代码啦

 

public class Parser {
private char lookahead;

public Parser() throws IOException {
        readch();
    }

// 能够处理多余的空白符
public boolean Is(char t) throws IOException {
while (lookahead == ' ' || lookahead == '\t') readch();
if (lookahead == t) return true;
else return false;
    }

public void readch() throws IOException {
        lookahead = (char) System.in.read();
    }

public void match(char t) throws IOException {
if (lookahead == t) {
            readch();
        }
else throw new Error("syntax error");
    }

public boolean digit() throws IOException {
if (Character.isDigit(lookahead)) {
            print(lookahead);
            readch();
return true;
        }
else return false;
    }

public void digits() throws IOException {
if (Is('-')) {
            match('-'); print('-'); digits();
        } else while (digit()) ;
    }


public void factor() throws IOException {
if (Is('(')) {
            match('('); expr(); 
if (!Is(')')) {
throw new Error("\"(\" 匹配错误");
            }
            match(')');
        } else {
            digits(); print(' ');
        }
    }


public void term() throws IOException {
        factor(); 
while (Is('*') || Is('/')) {
char t = lookahead; match(lookahead); factor(); print(t); print(' ');
        }
    }

public void expr() throws IOException {
        term();
while (Is('+') || Is('-')) {
char t = lookahead; match(lookahead); term(); print(t); print(' ');
        }
    }

public void print(char ch) {
        System.out.print(ch);
    }
}


public class Postfix {
public static void main(String[] args) {

try {
            Parser parser = new Parser();
            parser.expr();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}