Skip to content

编译原理课程设计 - 文法设计 & 词法分析 & LL(1)语法分析 & 语义分析(语法制导翻译)

Notifications You must be signed in to change notification settings

wasPrime/C_Compiler_Project

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

C_Compiler_Project

简介

编译原理课程设计 - 文法设计 & 词法分析 & LL(1)语法分析 & 语义分析(语法制导翻译)

文法设计Grammar

终结符

main int if else return + - * / = equal less_than less_euqal great_than great_equal not_equal ( ) { } id digit ; $

非终结符

<程序> <main函数> <返回类型> <变量类型> <复合语句> <语句序列> <语句> <语句递归> <定义语句> <赋初值> <赋值语句> <条件语句> <布尔表达式> <表达式> <项> <项递归> <因式> <因式递归> <关系运算符> <标识符> <无正负号常量>

文法产生式

非终结符命名 产生式
program <程序> ::= <main函数> $
main_fun <main函数> ::= <返回类型> main ( ) <复合语句>
return_type <返回类型> ::= <变量类型>
var_type <变量类型> ::= int
struct_statement <复合语句> ::= { <语句序列> }
statements_list <语句序列> ::= <语句> <语句递归> | ε
statement <语句> ::= <定义语句> | <赋值语句> | <条件语句> | <复合语句> | return <表达式> ;
statements_recursive <语句递归> ::= <语句> <语句递归> | ε
define_statement <定义语句> ::= <变量类型> <标识符> <赋初值> ;
assign_default <赋初值> ::= = <表达式> | ε
assign_statement <赋值语句> ::= <标识符> = <表达式>;
condition_statement <条件语句> ::= if ( <布尔表达式> ) <复合语句> else <复合语句>
bool_expression <布尔表达式> ::= <表达式> <关系运算符> <表达式>
expression <表达式> ::= <项> <项递归>
item <项> ::= <因式> <因式递归>
items_recursive <项递归> ::= + <项> <项递归> | - <项> <项递归> | ε
factor_recursive <因式递归> ::= * <因式> <因式递归> | / <因式> <因式递归> | ε
factor <因式> ::= <标识符> | <无正负号常量> | ( <表达式> )
relation_operator <关系运算符> ::= equal | less | less_equal | great_than | great_equal | not_equal
_identifier <标识符> ::= id
unsigned_const <无正负号常量> ::= digit

注意:

文法中以显式 $ 作为结束符号.

词法分析LexAnalyse

词法分析依据以下的DFA进行分析:

graph LR;
0(0)-- "空格或 \n 或\t" -->0;
0-- "字母" -->1(1);
1-- "数字/字母" -->1;
1-- "非字母且非数字" -->2((2));
0-- "数字" -->3(3);
3-- "数字" -->3;
3-- "非数字" -->4((4));
0-- "+" -->5((5));
0-- "-" -->6((6));
0-- "*" -->7((7));
0-- "/" -->8((8));
0-- "(" -->9((9));
0-- ")" -->10((10));
0-- "{" -->11((11));
0-- "}" -->12((12));
0-- ">" -->13((13));
13-- "=" -->14((14));
0-- "<" -->15((15));
15-- "=" -->16((16));
0-- "=" -->17((17));
17-- "=" -->18((18));
0-- "!" -->19(19);
19-- "!" -->20((20));
0-- ";" -->21((21));
0-- "$" -->22((22));
Loading

语法分析SynAnalyse

First集

非终结符 First集合列表
<程序> int
<main函数> int
<返回类型> int
<变量类型> int
<复合语句> {
<语句序列> int id if { return ε
<语句> int id if { return
<语句递归> int id if { return ε
<定义语句> int
<赋初值> = ε
<赋值语句> id
<条件语句> if
<布尔表达式> id digit (
<表达式> id digit (
<项递归> + - ε
<项> id digit (
<因式递归> * / ε
<因式> id digit (
<关系运算符> equal less_than less_equal great_than great_equal not_equal
<标识符> id
<无正负号常量> digit

Follow集

非终结符 First集合列表
<程序>
<main函数> $
<返回类型> main
<变量类型> main id
<复合语句> $
<语句序列> }
<语句> int id if { return }
<语句递归> }
<定义语句> int id if { return }
<赋初值> ;
<赋值语句> int id if { return }
<条件语句> int id if { return }
<布尔表达式> )
<表达式> ; equal less_than less_equal great_than great_equal not_equal )
<项递归> ; equal less_than less_equal great_than great_equal not_equal )
<项> + - ; equal less_than less_equal great_than great_equal not_equal )
<因式递归> + - ; equal less_than less_equal great_than great_equal not_equal )
<因式> * / + - ; equal less_than less_equal great_than great_equal not_equal )
<关系运算符> id digit (
<标识符> = * / + - ; equal less_than less_equal great_than great_equal not_equal )
<无正负号常量> * / + - ; equal less_than less_equal great_than great_equal not_equal )

LL(1)分析表

略(可知本文法无冲突)

小结

受水平所限, First集与Follow集手动生成, 然后根据递归子程序生成语法分析程序.

若水平足够, 可考虑由程序生成First集与Follow集, 继而生成LL(1)分析表. 根据符号栈和单词栈进行语法分析.

一般来说, 在发现语法错误时无法继续进行下去. 换句话说, 只能识别一个语法错误. 本代码中加入了一些可能产生的语法错误预测, 在不影响后续处理的前提下尽可能发现更多的语法错误, 提高效率.

语义分析(语法制导翻译)

在语法分析的递归子程序基础上插入一系列动作, 由表达式转化成四元式中间代码(不采用三元式有一定考量, 对于 if...else... 语句块的跳转语句不明确).

四元式表现形式

(<语句号>) <动作> <第1个输入> <第二个输入> <输出>

注意:

  1. 若某一单元格内无内容则使用下划线 _ 表示;

  2. 临时变量用 Ti 表示, 如第0个产生的临时变量记为 T0 (代码中有临时变量回收机制).

示例如下(语句号为随机, 仅供示例):

  • 定义语句: (1) assign int _ i 表示标识符 i 定义为 int 类型

  • 逻辑运算: (2) + i + 1 T0 表示 T0 = i + 1

  • 赋值语句: (3) = 1 _ i 表示 i = 1

  • 条件判断: (4) < i j T0 表示 T0 = i < j

  • 非真跳转: jne 意为 jump not equal true, (5) jne T0 _ (6) 表示当T0为假时跳转到第6条语句

About

编译原理课程设计 - 文法设计 & 词法分析 & LL(1)语法分析 & 语义分析(语法制导翻译)

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages