Lzu
词法分析器和语法分析器
词法分析器和语法分析器(非常适合学习)
注:1.本程序使用 c 语言实现,编译器使用 gcc,若在 windows 下执行可能会有库函数不支
持。在此特别推荐 linux 系统,写程序非常爽。
2.语法分析器中有算术表达式和逻辑表达式的左递归消除方式需要修改
3.程序运行方式:首先复制源代码,建立四个文件:
head.h scanner.h loadWord.h
然后进行编译:gcc parser.c
最后运行:./parser
test.p 为测试文件,内容如下:
test.p
parser.c
–o parser
program rightTest1;
{声明了一个整型的变量 i 和一个整型的数组 a}
var
i:=1;{给变量 i 赋初值为 1}dsf
while i<=4 do{依次从键盘给数组 a 的各个元素赋值}
read(
end.
4.语法分析使用的方法是纯正的递归下降语法分析
一、使用 LittleP+文法如下(每一条汉语产生式下对应的为英文版的产生式):
〈程序〉→〈程序首部〉 〈程序体〉 .
Prog→ProgHead ProgBody .
〈程序首部〉→ program〈程序名〉 ;
ProgHead→program ProgName ;
〈程序体〉→〈变量声明〉<分程序声明>〈复合语句〉
ProgBody→VarDecl SubProgDecl ComplexStmt
〈变量声明〉→ var〈变量定义列表〉|〈空〉
VarDecl→var VarDefList | ^
<变量定义列表> → 〈变量定义列表〉〈变量定义〉|〈变量定义〉
VarDefList→ VarDef VarDefList |VarDef
〈变量定义〉→〈变量名列表〉: <类型> ;
VarDef→VarNameList : Type ;
<变量名列表> → 〈变量名列表〉,〈变量名〉|〈变量名〉
VarNameList→ VarName , VarNameList
<类型> → <基本类型>|<数组>
Type→BaseType | Array
<基本类型> → integer | boolean
BaseType→integer | boolean
<数组> →array [〈下界〉..〈上界〉] of <基本类型>
Array→array [ LowBound .. UpBound ] of BaseType
| VarName
<下界> →<整数>
LowBound→Integer
<上界> →<整数>
UpBound→Integer
<分程序声明> → 〈分程序〉〈分程序声明〉|〈空〉
SubProgDecl →SubProg SubProgDecl | ^
〈分程序〉→ 〈分程序首部〉〈变量声明〉 〈复合语句〉
SubProg →SubProgHead VarDecl ComplexStmt
〈分程序首部〉→ procedure〈过程名〉( <形参列表> ); | function〈函数名〉( <形参列表> ) :
<基本类型>;
SubProgHead→procedure ProcName ( ForParaList ); |
function FunName ( ForParaList ) : BaseType;
<形参列表> → 〈形参定义〉 ,〈形参列表〉|〈形参定义〉|〈空〉
ForParaList→ForParaDef , ForParaList | ForParaDef | ^
〈形参定义〉→〈变量名列表〉: <基本类型>
ForParaDef→VarNameList : BaseType
〈复合语句〉→ begin〈语句块〉end
ComplexStmt→begin StmtBlock end
〈语句块〉→〈语句〉|〈语句块〉 ; 〈语句〉
StmtBlock→Stmt | Stmt StmtBlock ;
→
〈语句〉
〈赋值语句〉|〈条件语句〉|〈循环语句〉
|〈过程调用语句〉|〈复合语句〉|〈读写语句〉|〈空〉
Stmt→AsignStmt | CondStmt | LoopStmt | ProcCallStmt | ComplexStmt | RWStmt
<条件语句> → |
CondStmt→MatchStmt | OpenStmt
→ if <逻辑表达式> then else |
〈赋值语句〉|〈循环语句〉|〈过程调用语句〉|〈复合语句〉|〈读写语句〉|〈空〉
MatchStmt→if LogicExp then Stmt else MatchStmt
| AsignStmt | LoopStmt | ProcCallStmt |
|
^
ComplexStmt | RWStmt | ^
→ if < 逻 辑 表 达 式 > then < 语 句 > | if < 逻 辑 表 达 式 > then
else
OpenStmt→if LogicExp then Stmt | if LogicExp then MatchStmt else OpenStmt
〈赋值语句〉→〈左部〉:= 〈右部〉
AssignStmt→Left := Right
〈左部〉→〈变量名〉|〈变量名〉[ 算术表达式 ]
Left→VarName | VarName [ ArithExp ]
〈右部〉→〈算术表达式〉
Right→ArithExp
〈循环语句〉→ while〈逻辑表达式〉do〈语句〉
LoopStmt→while LogicExp do Stmt
〈过程调用语句〉→〈过程名〉( <实参列表> ) |〈函数名〉( <实参列表> )
ProcCallStmt→ProcName ( RealParaList ) | FunName ( RealParaList )
<实参列表> → 〈算术表达式〉| 〈算术表达式〉,〈实参列表〉|〈空〉
RealParaList→ArithExp | ArithExp , RealParaList | ^
〈读写语句〉→ read ( <变量名列表> ) | write ( <变量名列表> )
WRStmt →read ( VarNameList ) | write ( VarNameList )
<逻辑表达式> → 〈逻辑项〉| 〈逻辑项〉〈逻辑运算符〉〈逻辑项〉
LogicExp →LogicItem | LogicItem LogicOp LogicItem
<逻辑运算符> → and | or
LogicOp →and | or
<逻辑项> → <关系表达式> |〈变量名〉| not <逻辑项> |true | false
LogicItem→RelExp | VarName | not LogicItem | true | false
<关系表达式> →〈算术表达式〉 〈关系运算符〉 〈算术表达式〉
RelExp→ArithExp RelOp ArithExp
<算术表达式> → 〈项〉| 〈算术表达式〉 〈加运算符〉 〈项〉
ArithExp→Item | Item AddOp ArithExp
<项> → 〈因子〉| 〈项〉 〈乘运算符〉 〈因子〉
Item→Factor | Factor MulOp Item
〈因子〉→〈变量名〉|(〈算术表达式〉)|〈函数名〉(<实参列表>) |〈变量名〉[ 算术表达
式 ] |〈整数〉
Factor →VarName | ( ArithExp ) | FunName ( RealParaList ) | VarName [ ArithExp ] | Integer
〈程序名〉→〈标识符〉
ProgName→ID
〈变量名〉→〈标识符〉
VarName→ID
〈过程名〉→〈标识符〉
ProcName→ID
〈函数名〉→〈标识符〉
FunName→ID
〈标识符〉→〈字母〉|〈标识符〉〈字母〉|〈标识符〉〈数字〉
ID→Letter | Letter ID | ID Number
〈整数〉→〈数字〉|〈整数〉 〈数字〉
Integer→Number | Number Integer
〈关系运算符〉→ < | <= | > | >= | = | <>
RelOp →< | <= | > | >= | = | <>
〈加运算符〉→ + | -
AddOp→+ | -
〈乘运算符〉→ * | /
MulOp→* | /
〈字母〉→ a|b|...|x|y|z
Letter →a | b | … | x | y | z
〈数字〉→ 1|2|3|4|5|6|7|8|9|0
Number→1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0
二、终结符对应的类型如下:
单词符号
program
var
integer
boolean
array
of
procedure
function
begin
end
if
then
else
while
do
read
write
and
or
not
true
类型码
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
单词符号
标识符
整型常量
<
<=
>
>=
=
<>
+
-
*
/
:=
[
]
..
.
(
)
,
;
类型码
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
false
21
:
43
三、程序(程序一共包括四个文件:三个头文件,一个主文件)
1.head.h(包括一些全局变量和函数声明)
#include
#include
#include
#include
#include
#include
#include
#include
//the max length of the word
#define M 20
#define TRUE 1
#define FALSE 0
//the pointer of opened file
FILE* fp = NULL;
//the first address of word cache
static struct Word* front = NULL;
//the current word pointer
static struct Word* w;
//the struct of word
struct Word
{
int type;
char word[M];
int row;
struct Word* next;
};
///////////////////the declearation of functions in parser.c //////////////////////
void parser();
void move();
void error(char* message);
void match(int type);
int test(int type);
void prog();
void progHead();
void progName();
void id();
void progBody();
void varDecl();
void varDefList();
void varDef();
void type();
void baseType();
void array();
void lowBound();
void upBound();
void integer();
void varNameList();
void varName();
void subProgDecl();
void subProg();
void subProgHead();
void funName();
void forParaList();
void forParaDef();
void complexStmt();
void stmtBlock();
//void stmt();
int stmt();
//void assignProgCallStmt();
int assignProgCallStmt();
void assignStmt();
void left();
void right();
void arithExp();
void item();
void mulOp();
void addOp();
void factor();
void assignVarFun();
void procCallStmt();
void realParaList();
void condStmt();
void loopStmt();
void rwStmt();
void logicExp();
void logicItem();
void assignVarRel();
void relExp();
void relOp();
2.scanner.h(此文件为词法分析器)
//#include"head.h"
//#include"loadWord.h"
//将文件映射到内存,并返回在内存中的首地址
char* mapFile(char* fileName,int* fileSize)
{
//文件标识
int fd;
//文件映射到内存的首地址
char* start;
//获取文件的相关信息
struct stat st;
//打开文件
fd = open(fileName,O_RDONLY);
//若打开文件失败
if( fd==-1 )
{
printf("no such file or directory!\n");
exit(0);
}
//获取文件的相关信息
fstat(fd,&st);
//将文件映射到内存并获取首地址
start=mmap(NULL,st.st_size,PROT_READ,MAP_PRIVATE,fd,0);
//若映射失败,则返回空地址
if(start == MAP_FAILED) return NULL;
//获取文件的大小
(*fileSize) = st.st_size;
//关闭文件
close(fd);
//返回映射到内存的首地址
return start;
}
//解除文件文件在内存中的映射
void munmapFile(char* start,int fileSize)
{
munmap(start,fileSize);
}
//test is the character between 'a' and 'z' or between 'A' and 'Z'
int isLetter(char c)
{
if( ((c>='a')&&(c<='z'))||((c>='A')&&(c<='Z')) )
{
return TRUE;
}
else
{
}
}
return FALSE;
//test is the character between '0' and '9'
int isNumber(char c)
{
if( (c>='0')&&(c<='9') )
{
return TRUE;
}
else
{
}
}
return FALSE;
//测试是否为算术运算符 +,-,*,/
int isArithOperator(char c)
{
switch(c)
{
case '+':
case '-':
case '*':
case '/':return TRUE;
default:return FALSE;
}
}
//测试是否为关键字
int isKeyword(char* s)