语法分析： 一个例子
5.00/5 (8投票s)
自顶向下解析
下载源代码
- 继续遵循语法文法定义的产生式规则，var() 将调用 mvars()，program() 调用 block()，mvars() 递归调用自身，block() 调用 var() 和 stats()，... 以此类推，用于 in()、f()、t()、assign()、loop() 等。最后，ro() 函数。
引言
在分析输入源文件的语法之前，扫描标记是第一步。上一篇文章 词法分析器 提供了一个扫描器的例子。现在，本文将提供一个解析器（或语法分析器）的例子。整个任务包括以下规则和要求：
1/4：词法规则
- 不区分大小写
- 所有英文字母（大写和小写）、数字以及下方所示的额外字符，加上空格
- 标识符
- 以字母开头，后面可以跟任意数量的字母
- 假设标识符长度不超过 8 个字符
- 关键字（保留字），包括：start finish then if repeat var int float do read print void return dummy program
- 关系运算符，包括： < > =!= => =< ==
- 其他运算符，包括：= : + - * / %
- 分隔符，包括：. ( ) , { } ; [ ]
- 数字
- 任意十进制数字序列，无符号
- 假设数字长度不超过 8 位数字
- 其他假设
- 除非改变标记的含义（如 x y 与 xy），否则不需要空格来分隔标记
- 注释以 // 开头，以换行符结束
- 做出任何合理的假设和必要的验证。例如，如果发现无效符号，显示带有行号的错误消息，然后中止程序
这一步对应于从输入源文件中“词法分析”（或扫描）标记（也称为符号）。每个标记都是有意义的字符序列，例如数字、运算符或标识符等。
2/3：语法规则
这一步对应于“语法分析”（或解析）。这里采用自顶向下解析，因为它更容易实现（但功能较弱）。我们遵循最左推导，或 LL(k)，其中 k = 1 是前瞻（look-ahead），用于决定遵循哪个推导（这意味着通过下一个字符，就可以决定应用哪个规则）。
因此，我们需要验证上述语法规则是否为 LL(1)，或者根据需要将其重写为等效形式。
3/4：解析树
扫描和解析成功后，构建解析树，每个节点包含零个、一个或多个标记。每个标记都有实例、标记类型和行号。
4/4：其他要求
程序的调用方式是：
testParser [文件名]
其中输入源文件是 filename.lan（.lan 扩展名是隐含的）。如果未指定文件名，程序将通过重定向文件从键盘读取相同的数据。
例如：testParser < filename.lan
计划
这是定义程序文件依赖关系的 Makefile。
CC = gcc
PROG = testParser
$(PROG): main.o scanner.o parser.o
$(CC) -o $(PROG) main.o scanner.o parser.o
main.o : main.c token.h scanner.h parser.h
$(CC) -c main.c
scanner.o : scanner.c token.h scanner.h symdef.h
$(CC) -c scanner.c
parser.o : parser.c parser.h token.h
$(CC) -c parser.c
.PHONY: clean
clean:
/usr/bin/rm -rf core $(PROG) *.o
在 上一篇文章 中，标记化已经完成，但没有利用 Token 和 TokenType 数据结构来服务于解析和构建解析树的目的。因此，扫描器现在将重写。但首先，让我们看看 token.h 中定义的数据结构。
#define MAX 9 // max length of each word string, not including '\0'
extern int lineNum;
typedef enum {
// Identifier: begin with a letter, and continue with any number
// of letters. No ID is longer than MAX
IDtk,
// Keywords (start finish then if repeat var int float do
// read print void return dummy program)
STARTtk, FINISHtk, THENtk, IFtk, REPEATtk, VARtk, INTtk, FLOATtk,
DOtk, READtk, PRINTtk, VOIDtk, RETURNtk, DUMMYtk, PROGRAMtk,
// Number: sequence of decimal digits, no sign, no longer than MAX digits
NUMBERtk,
// Relational Operators (== < > =!= => =<)
EQUALtk, GREATERtk, LESStk, DIFFtk, GREATEREQtk, LESSEQtk,
// Other operators (= : + - * / %)
ASSIGNtk, COLONtk, ADDtk, SUBTRACTtk, MULtk, DIVtk, REMAINDERtk,
// Delimiters (. ( ) , { } ; [ ])
DOTtk, LEFTPAtk, RIGHTPAtk, COMMAtk, LEFTBRACEtk, RIGHTBRACEtk,
SEMICOLONtk, LEFTBRACKETtk, RIGHTBRACKETtk,
NAtk, // N/A token
EOFtk
} TokenType;
struct tokenTag {
char str[MAX];
TokenType tokenType;
int lineNum;
struct tokenTag *next; // linked-list, used for parse tree
};
typedef struct tokenTag Token;
extern int numToken;
extern Token *tokens; // list of all tokens (array of numToken)
如上所述，每个 Token 具有以下元素：（1）标记实例（字符串），（2）标记类型，（3）在输入源文件中找到的行号，以及（4）一个稍后用于解析树的指针。
main.c
main() 函数执行必要的验证，如命令行参数、文件存在性、单词的最大长度、无效字符等，这些与 上一篇文章 中的内容没有改变。在所有这些都完成并且 OK 之后，它会调用扫描器来完成工作。
/*---------Begin Scanner-------------*/
printf("%10s \t Line number \t %s\n\n", "Token instance", "Token type");
numToken = 0; // extern var
//Token *tokens = (Token *) malloc(numToken * sizeof(Token));
tokens = (Token *) malloc(numToken * sizeof(Token)); // extern var
do {
numToken++;
tokens = (Token *)realloc(tokens, numToken * sizeof(Token));
tokens[numToken - 1] = scanner(filePtr);
printToken(tokens[numToken - 1]);
} while (tokens[numToken - 1].tokenType != EOFtk);
/*---------/End Scanner-------------*/
数组 tokens（大小为 numtoken）是（以防万一）用来存储扫描器遍历输入源文件时找到的所有标记。注意 EOFtk 用于终止扫描器，而不是 EOF。
之后，main() 调用解析器，关闭文件，完成。
parser(filePtr);
fclose(filePtr);
return 0;
扫描器 (scanner.c)
symdef.h
首先，为了方便起见，symdef.h 包含数据定义（基于词法规则）。
char *keywords[15] = {"start", "finish", "then", "if", "repeat", "var",
"int", "float", "do", "read", "print", "void", "return", "dummy", "program"};
char *relationalOperators[] = {"==", "<", ">", "=!=", "=>", "=<"};
char otherOperators[6] = {':', '+', '-', '*', '/', '%'};
char delimiters[9] = {'.', '(', ')', ',', '{', '}', ';', '[', ']'};
char word[MAX];
int wi = 0; // index of word string
char numStr[MAX];
int ni = 0;
Token scanner(FILE *) 函数
int numToken = 0; // define extern var declared from token.h
int lineNum = 1; /// silimilar, extern var from token.h
Token *tokens = NULL; // define extern var
Token scanner(FILE *filePtr) {
Token token;
char ch;
while ((ch = fgetc(filePtr)) != EOF) {
if (ch == '\n')
lineNum++;
// Ignore comment starting with // to the end of line
if (ch == '/') {
if (fgetc(filePtr) == '/') {
while ((ch = fgetc(filePtr)) != '\n') {}
lineNum++;
} else
fseek(filePtr, -1, SEEK_CUR);
}
if (isalpha(ch)) {
word[wi++] = ch;
while (isalpha(ch = fgetc(filePtr))) {
word[wi++] = ch;
}
word[wi] = '\0';
wi = 0;
strcpy(token.str, word);
if (isKeyword(word)) {
token.tokenType = getTokenTypeOfKeyword(word);
} else {
token.tokenType = IDtk;
}
token.lineNum = lineNum;
fseek(filePtr, -1, SEEK_CUR);
return token;
}
else if (isdigit(ch)) {
numStr[ni++] = ch;
while (isdigit(ch = fgetc(filePtr))) {
numStr[ni++] = ch;
}
numStr[ni] = '\0';
ni = 0;
strcpy(token.str, numStr);
token.tokenType = NUMBERtk;
token.lineNum = lineNum;
fseek(filePtr, -1, SEEK_CUR);
return token;
}
else if (ispunct(ch)) {
if (isDelimiter(ch)) {
token.tokenType = getTokenTypeOfDelimiter(ch);
token.lineNum = lineNum;
char str[2];
str[0] = ch;
str[1] = '\0';
strcpy(token.str, str);
return token;
}
else if (isOtherOperators(ch)) {
token.tokenType = getTokenTypeOfOtherOperator(ch);
token.lineNum = lineNum;
char str[2];
str[0] = ch;
str[1] = '\0';
strcpy(token.str, str);
return token;
}
else if (isStartRelationalOperator(ch)) {
if (ch == '<' || ch == '>') {
token.lineNum = lineNum;
if (ch == '<') {
token.tokenType = LESStk;
strcpy(token.str, "<");
} else {
token.tokenType = GREATERtk;
strcpy(token.str, ">");
}
return token;
}
else if (ch == '=') {
if ((ch = fgetc(filePtr)) == '=' || ch == '>' || ch == '<') {
token.lineNum = lineNum;
if (ch == '=') {
token.tokenType = EQUALtk;
strcpy(token.str, "==");
} else if (ch == '>') {
token.tokenType = GREATEREQtk;
strcpy(token.str, "=>");
} else {
token.tokenType = LESSEQtk;
strcpy(token.str, "=<");
}
return token;
} else if (ch == '!') {
if ((ch = fgetc(filePtr)) == '=') {
token.lineNum = lineNum;
token.tokenType = DIFFtk;
strcpy(token.str, "=!=");
return token;
} else
fseek(filePtr, -1, SEEK_CUR);
} else
fseek(filePtr, -1, SEEK_CUR);
}
}
} // end if ispunct
} // end while
token.tokenType = EOFtk;
return token;
}
注意
- 想法是“向前看一个字符”，以决定下一个标记是什么（或可能是）什么。
- fseek(filePtr, -1, SEEK_CUR) 用于在需要时回退一个字符。
- 除了提供的内置函数（如 isalpha(ch)、isdigit(ch) 和 ispunct(ch)）之外，还有一些辅助函数用于检查字符。
int isKeyword(char *str) {
int i;
int result = 0; // false
for (i = 0; i < 15; i++) {
if (!strcasecmp(keywords[i], str))
result = 1;
}
return result;
}
int isDelimiter(char c) {
int i;
int result = 0; // false
for (i = 0; i < 9; i++) {
if (delimiters[i] == c)
result = 1;
}
return result;
}
int isOtherOperators(char c) {
int i;
int result = 0; // false
for (i = 0; i < 6; i++) {
if (otherOperators[i] == c)
result = 1;
}
return result;
}
int isStartRelationalOperator(char c) {
int i;
int result = 0; // false
if (c == '=' || c == '<' || c == '>') {
result = 1;
}
return result;
}
注意：数字 6、9、15（预先指定的其他运算符、分隔符和关键字的数量）是硬编码的，这不应该。它们应该以与 token.h 中的 MAX 类似的方式定义。
Scanner(FILE *) 的最后三个辅助函数
TokenType getTokenTypeOfKeyword(char *word) {
if (strcasecmp(word, "start") == 0) return STARTtk;
if (strcasecmp(word, "finish") == 0) return FINISHtk;
//... similar
}
TokenType getTokenTypeOfDelimiter(char ch) {
if (ch == '.') return DOTtk;
if (ch == '(') return LEFTPAtk;
// ... similar
}
TokenType getTokenTypeOfOtherOperator(char ch) {
if (ch == '=') return ASSIGNtk;
if (ch == ':') return COLONtk;
// ... similar
}
打印标记的函数也定义在 scanner.c 中。
解析器和解析树
遵循上面的产生式规则（语法文法），parser.h 声明了两个数据结构。
void parser(FILE *);
// Represent non-terminal token nodes
typedef enum {
programNode, blockNode, varNode, mvarsNode, exprNode, xNode,
tNode, yNode, fNode, rNode, statsNode, mStatNode, statNode,
inNode, outNode, ifNode, loopNode, assignNode, roNode
} NodeType;
/*------- TREE -------*/
struct nodeTag {
NodeType nodeType;
Token *tokenPtr; // linked-list of tokens of this node
struct nodeTag *child1; // usually only up to 3 children needed
struct nodeTag *child2;
struct nodeTag *child3;
struct nodeTag *child4; // but for and , 4 children needed
};
typedef struct nodeTag Node;
注意：请查看 parser.h 中的语法规则和数据类型，以便更容易阅读本文的其余部分。
parser.c
parser.c 以以下方式开始：
Token tk = {"N/A", NAtk, 0};
初始化全局 token tk 变量，该变量在整个解析过程中使用，并开始由 main() 调用的函数。
void parser(FILE *filePtr) {
lineNum = 1; // reset line number
fP = filePtr;
rewind(fP);
tk = scanner(fP);
Node *root = NULL;
root = program();
if (tk.tokenType == EOFtk)
printf("Parse OK! \n");
else {
exit(1);
}
printf("\n*-----Parse Tree-----*\n");
printParseTree(root, 0);
return;
}
正如我们所见，program() 函数对应于上面第一个产生式规则（语法文法），其定义如下：
Node * program() {
Node *node = getNode(programNode);
node->child1 = var();
if (tk.tokenType == DOtk) {
tk = scanner(fP);
} else {
printf("ERROR: expect DOtk or VARtk, but received %s on line #%d \n", tk.str, tk.lineNum);
exit(1);
}
node->child2 = block();
if (tk.tokenType == RETURNtk) {
tk = scanner(fP);
return node;
} else {
printf("ERROR: expect RETURNtk, bu received %s on line #%d \n", tk.str, tk.lineNum);
exit(1);
}
}
注意：Node *getNode (NodeType) 函数返回一个由传递给它的 NodeType 参数标记的新节点。
Node *getNode(NodeType nodeType) {
Node *node;
node = (Node *) malloc(sizeof(Node));
node->nodeType = nodeType;
node->tokenPtr = NULL;
node->child1 = node->child2 = node->child3 = node->child4 = NULL;
return node;
}
同样，基于语法规则，var() 对应于带 < var > 的产生式规则，并定义如下：
Node * var() {
Node *node = getNode(varNode);
if (tk.tokenType == VARtk) {
tk = scanner(fP);
if (tk.tokenType == IDtk) {
insertToken(node, tk);
tk = scanner(fP);
} else {
printf("ERROR: expect IDtk, but received %s on line #%d \n", tk.str, tk.lineNum);
exit(1);
}
node->child1 = mvars();
if (tk.tokenType == DOTtk) {
tk = scanner(fP);
return node;
} else {
printf("ERROR: expect DOTtk, but received %s on line #%d \n", tk.str, tk.lineNum);
exit(1);
}
}
else {
return node; // predict --> empty
}
}
注意
- 产生式规则 < type > 被移除并直接替换到 < var > 产生式规则中，如下所示：
< var > --> empty | var ID < mvars > .
- insertToken(Node *, Token) 函数将在稍后展示。- 继续遵循语法文法定义的产生式规则，var() 将调用 mvars()，program() 调用 block()，mvars() 递归调用自身，block() 调用 var() 和 stats()，... 以此类推，用于 in()、f()、t()、assign()、loop() 等。最后，ro() 函数。
Node * ro() {
Node *node = getNode(roNode);
if (tk.tokenType == LESSEQtk) {
insertToken(node, tk);
tk = scanner(fP);
return node;
} else if (tk.tokenType == GREATEREQtk) {
insertToken(node, tk);
tk = scanner(fP);
return node;
} else if (tk.tokenType == EQUALtk) {
insertToken(node, tk);
tk = scanner(fP);
return node;
} else if (tk.tokenType == GREATERtk) {
insertToken(node, tk);
tk = scanner(fP);
return node;
} else if (tk.tokenType == LESStk) {
insertToken(node, tk);
tk = scanner(fP);
return node;
} else if (tk.tokenType == DIFFtk) {
insertToken(node, tk);
tk = scanner(fP);
return node;
} else {
printf("ERROR: expect relational operator, but received %s on line #%d \n",
tk.str, tk.lineNum);
exit(1);
}
}
insertToken(Node *, Token) 函数用于将新 Token 插入到树节点的标记链表的末尾。
Token *getTokenPtr(Token tk) {
Token *tokenPtr = (Token *) malloc(sizeof(Token));
strcpy(tokenPtr->str, tk.str);
tokenPtr->lineNum = tk.lineNum;
tokenPtr->tokenType = tk.tokenType;
return tokenPtr;
}
void insertToken(Node *node, Token tk) {
Token *new = getTokenPtr(tk);
if (node->tokenPtr == NULL) {
node->tokenPtr = new;
} else {
Token *tmp = node->tokenPtr;
while (tmp->next != NULL) {
tmp = tmp->next;
}
tmp->next = new;
}
}
此时，我们准备打印解析树。
// Hard-code to map with enum NodeType declared in parser.h
char *nodeTypeStrArr[] = {
"", "", ... similar ... , "", ""
};
// Hard-coded to map with enum TokenType declared in token.h
char *tokenStrArr[] = {
"IDtk",
"STARTtk", "FINISHtk", "THENtk", "IFtk",
... similar
"NAtk", "EOFtk"
};
void printParseTree(Node *root, int level) {
if (root == NULL) return;
printf("%*s" "%d %s ", level * 4, "", level, nodeTypeStrArr[root->nodeType]);
Token *tmp = root->tokenPtr;
int isTokenFound = 0; // false
if (tmp != NULL) {
isTokenFound = 1;
printf("{Token(s) found: ");
}
while (tmp != NULL) {
int isLastToken = 0; // false
printf("%s (%s, #%d)", tmp->str, tokenStrArr[tmp->tokenType], tmp->lineNum);
tmp = tmp->next;
if (tmp == NULL)
isLastToken = 1;
if (! isLastToken) {
printf(", and ");
}
}
if (isTokenFound) {
printf("}");
}
printf("\n");
printParseTree(root->child1, level + 1);
printParseTree(root->child2, level + 1);
printParseTree(root->child3, level + 1);
printParseTree(root->child4, level + 1);
}
示例输出
扫描器输出
解析一个“坏的”（语法无效）文件
解析一个有效的文件