相比词法分析器，构造语法分析器的方法有很多，其中手写起来最简单的自然是递归下降的方法了。
文法
要实现一种语言的分析器，我们需要先写出这种语言的上下文无关文法(Context-free grammer)，我选择语言的文法如下：
P -> S $
S -> S ; S
S -> id = EXP
S -> print ( EXPS )
EXPS -> EXP
EXPS -> EXPS , EXP
EXP -> int
EXP -> id
EXP -> EXP OP EXP
EXP -> ( EXP )
OP -> +
OP -> -
OP -> *
OP -> /
其中大写单词表示非终结符，小写字母和符号表示终结符。
处理文法
递归下降分析器的构造方法非常简单，简单来说，就是为每一个非终结符写一个递归函数，函数中对该终结符可能转换成的所有情况的第一个token进行判断，做出对应的处理，例如，S的函数形式如下(要注意的是这个函数是错的，只是为了表现形式，下面会说明)：
void S(){
switch(current_token){
case S:
S(); eat(';'); S(); break;
case id:
eat(id); eat('='); EXP(); break;
case print:
eat(print); eat('('); EXPS(); eat(')'); break;
default:
error_exit();
}
}
看起来很简单吧？但是上面的函数是有问题的，函数只会执行case S的情况，并将无限德递归下去，这称为左递归。
这不是我们方法的问题，而是文法格式的问题，递归下降方法只能处理没有左递归和左因子的文法，我们需要消除它。
消除左递归
类似
E -> E + T
E -> T
的文法是左递归的，我们可以通过引入一个新的非终结符来消除它，结果如下：
E -> T E'
E' -> + T
E' ->
上面展示的并不是一种模板，而是一种思想，我们的文法中，在非终结符EXP,S中也出现了左递归的情况，但是要复杂得多，你需要理解消除左递归的思想来解决它们。
提取左因子
考虑文法中的EXPS，我们发现我们无法根据其转换的第一个符号来判断下一步该做什么。
当一个非终结符的不同转换的前几个符号是相同的符号，这种情况也会发生类似左递归的问题，我们需要通过提取左因子的方法消除它。
类似
S -> E + E
S -> E
的文法是有问题的，依然是引入一个新的非终结符：
S -> E S'
S' -> + E
S' ->
最终的文法
在消除了EXP 和 S的左递归，提取了EXPS的左因子之后，文法如下：
P -> S $
S -> id = EXP S'
S -> print ( EXP S ) S'
S' -> ; S
S' ->
EXPS -> EXP EXPS'
EXPS' -> , EXPS
EXPS' ->
EXP -> ( EXP )
EXP -> int EXP'
EXP -> id EXP'
EXP' -> OP EXP
EXP' ->
OP -> +
OP -> -
OP -> *
OP -> /
构建分析器
现在让我们从语言到结果，构造我们的代码。
词法分析（myrdp.l）
首先，我们需要把字符串形式的语言转换成token串，这一步我们需要词法分析器，我使用flex完成这一步的工作，在分析过程中存储每个token的类型和值，存储类型的具体定义见下面的 myrdp.h 文件代码，代码如下：
%{
#include "myrdp.h"
#include <iostream>
#include <stdlib.h>
#include <string>
using namespace myrdp;
%}
%%
; tokens.push_back(Token(SEMICOLON));
= tokens.push_back(Token(ASSIGN));
\( tokens.push_back(Token(LPAREN));
\) tokens.push_back(Token(RPAREN));
, tokens.push_back(Token(COMMA));
\+ tokens.push_back(Token(PLUS));
- tokens.push_back(Token(MINUS));
\* tokens.push_back(Token(TIMES));
\/ tokens.push_back(Token(DIV));
print tokens.push_back(Token(PRINT));
[0-9]+ tokens.push_back(Token(INT,atoi(yytext)));
[a-zA-Z]+[a-zA-Z0-9]* {
tokens.push_back(Token(ID,std::string(yytext)));
}
[ \t\n] ;
. std::cout<<"invalid input:"<<yytext<<std::endl;
%%
int yywrap(){
return 1;
}
语法分析(myrdp.h myrdp.cpp)
现在我们得到了一个存储了token的vector，我们只要按照上面所说的构建方法，从头到尾以递归的方式遍历一遍vector就可以得到结果，代码很简单，直接看代码吧。
程序的入口结构，即写在main函数里的部分
yyin = fopen(argv[1],"r");
yylex();
prog();
关键结构的定义和函数声明见myrdp.h
myrdp.h
#pragma once
#include <vector>
#include <string>
#include <map>
namespace myrdp{
/*token 类型*/
enum Type{
SEMICOLON=1, ASSIGN, PRINT,
LPAREN, RPAREN, COMMA,
INT, ID, PLUS,
MINUS, TIMES, DIV
};
/*token值存储*/
struct Value{
int num;
std::string id;
Value() = default;
Value(int _n):num(_n){}
Value(const std::string& _i):id(_i){}
~Value(){}
};
/*token结构*/
struct Token{
Type type;
Value value;
Token(Type _t):type(_t),value(0){}
Token(Type _t,int _v):type(_t),value(_v){}
Token(Type _t,const std::string& _i):type(_t),value(_i){}
};
extern std::vector<Token> tokens;
extern std::map<std::string,int> table;
extern int cur;
extern std::vector<std::string> TypeToString;
void prog();
void stm();
void stm_prime();
void exps();
void exps_prime(int);
int exp();
int exp_prime(int);
}
具体函数和变量的定义
myrdp.cpp
#include <vector>
#include <cstdlib>
#include <iostream>
#include <map>
#include "myrdp.h"
namespace myrdp{
std::vector<Token> tokens;
std::map<std::string,int> table;
int cur = 0;
std::vector<std::string> TypeToString = {
"0","SEMICOLON", "ASSIGN", "PRINT",
"LPAREN", "RPAREN", "COMMA",
"INT", "ID", "PLUS",
"MINUS", "TIMES", "DIV"
};
//prog,stm,exps,exp
void err_exit(){
std::cout<<"syntax error in token: ";
std::cout<<TypeToString[myrdp::tokens[myrdp::cur].type]<<std::endl;
exit(EXIT_FAILURE);
}
void eat(Type t){
if(t==myrdp::tokens[myrdp::cur].type){
myrdp::cur++;
}else{
err_exit();
}
}
void prog(){
stm();
}
void stm(){
const Token &tok = myrdp::tokens[myrdp::cur];
switch(tok.type){
case ID:
myrdp::cur++;
eat(ASSIGN);
myrdp::table[tok.value.id]=exp();
stm_prime();
break;
case PRINT:
eat(PRINT);
eat(LPAREN);
exps();
eat(RPAREN);
stm_prime();
break;
default:
err_exit();
}
}
void stm_prime(){
const Token &tok = myrdp::tokens[myrdp::cur];
switch(tok.type){
case SEMICOLON:
eat(SEMICOLON);
stm();
break;
default:
break;
}
}
void exps(){
exps_prime(exp());
}
void exps_prime(int a){
const Token &tok = myrdp::tokens[myrdp::cur];
switch(tok.type){
case COMMA:
eat(COMMA);
exps_prime(exp());
break;
default:
std::cout<<a<<" ";
break;
}
}
int exp(){
const Token &tok = myrdp::tokens[myrdp::cur];
int a;
switch(tok.type){
case LPAREN:
eat(LPAREN);
a = exp();
eat(RPAREN);
return a;
case ID:
a = myrdp::table[tok.value.id];myrdp::cur++;
return exp_prime(a);
case INT:
a = tok.value.num;cur++;
return exp_prime(a);
default:
err_exit();
break;
}
//cannot reach here
return 0;
}
int exp_prime(int a){
const Token &tok = myrdp::tokens[myrdp::cur];
switch(tok.type){
case PLUS:
eat(PLUS);
return a+exp();
case MINUS:
eat(MINUS);
return a-exp();
case TIMES:
eat(TIMES);
return a*exp();
case DIV:
eat(DIV);
return a/exp();
default:
return a;
}
}
}
网友评论