CPU0 处理器的架构及应用
2021/10/2 6:10:59
本文主要是介绍CPU0 处理器的架构及应用,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
CPU0 处理器的架构及应用
简介
CPU0 是一个 32 位的处理器,包含 R0..R15, IR, MAR, MDR 等缓存器,结构如下图所示。
图 1 :CPU0 处理器的结构
其中各个缓存器的用途如下所示:
IR |
指令缓存器 |
R0 |
常数缓存器, 值永远为 0。 |
R1~R11 |
通用型缓存器。 |
R12 |
状态缓存器 (Status Word : SW) |
R13 |
堆栈指针缓存器 (Stack Pointer : SP) |
R14 |
链接缓存器 (Link Register : LR) |
R15 |
程序计数器 (Program Counter : PC) |
MAR |
地址缓存器 (Memory Address Register) |
MDR |
数据缓存器 (Memory Data Register) |
CPU0 的指令集
CPU0 的指令分为三种类型,L 型通常为加载储存指令、A 型以算术指令为主、J 型则通常为跳跃指令,下图显示了这三种类型指令的编码格式。
图 2:CPU0 的三种指令格式
以下是 CPU0 处理器的指令表格式
表 1 :CPU0 的指令表
在第二版的 CPU0_v2 中,补上了以下指令:
类型 |
格式 |
指令 |
OP |
说明 |
语法 |
语意 |
浮点运算 |
A |
FADD |
41 |
浮点加法 |
FADD Ra, Rb, Rc |
Ra = Rb + Rc |
浮点运算 |
A |
FSUB |
42 |
浮点减法 |
FSUB Ra, Rb, Rc |
Ra = Rb + Rc |
浮点运算 |
A |
FMUL |
43 |
浮点乘法 |
FMUL Ra, Rb, Rc |
Ra = Rb * Rc |
浮点运算 |
A |
FADD |
44 |
浮点除法 |
FDIV Ra, Rb, Rc |
Ra = Rb / Rc |
中断处理 |
J |
IRET |
2D |
中断返回 |
IRET |
PC = LR; INT 0 |
状态缓存器
CPU0 的状态缓存器,包含 N, Z, C, V 等状态,以及 I, T 等中断模式位。结构如下图所示。
图 3:CPU0 的状态缓存器
当 CMP Ra, Rb 指令执行时,状态标志会因而改变。
假如 Ra > Rb, 则会设定状态 N=0, Z=0
假如 Ra < Rb, 则会设定状态 N=1, Z=0
假如 Ra = Rb, 则会设定状态 N=0, Z=1
于是条件式跳跃的 JGT, JLT, JGE, JLE, JEQ, JNE 等指令,就可以根据状态缓存器中的 N, Z 标志进行跳跃操作。
指令的执行步骤
CPU0在执行一个指令时,必须经过取指、译码与执行等三大阶段。
- 提取阶段
- 操作1、提取指令 :IR = [PC]
- 操作2、更新计数器 :PC = PC + 4
- 解碼阶段
- 操作3、解碼 :控制单元对IR进行译码后,设定数据流向开关与 ALU 的运算模式
- 运行时间
- 操作4、执行 :数据流入 ALU,经过运算后,流回指定的缓存器
V-OS: 横跨操作系统与硬件的虚拟机系统
- 设计一个虚拟机系统,可以将 CPU A, B, C, D, E … 模拟成另外任何一种 CPU,这样是否能解决所有的跨平台问题呢?
- QEMU 其实可以做到类似的操作,想法与 QEMU 不同点在于 QEMU 是在操作系统层次之上的,做法是在操作系统层次之下的。
- 这样子就可以将在任何一个 CPU 上,跑另一个操作系统的程序,但是,不知速度会比 QEMU 快还是慢呢?
- 这种做法姑且可以想象为「云端虚拟机」!
- 不知大家觉得可能吗?有用吗?
图一:V-OS 系统的架构图
CC1 编译程序
为了说明编译程序是如何设计出来的,在开放计算机计划中,设计了一个功能完备,简化过的 C 语言,这个语言称为 C1 语言,是 C0 语言的扩充版。
CC1 编译程序是一个 C1 语言的编译程序,具有完成的编译程序功能。在程序设计上,CC1 又被进一步拆解为 1. 词汇分析 2. 语法分析 3. 语意分析 4. 中间码产生 5. 汇编语言产生 等阶段,这所有的阶段,都会存取一个共同的数据结构,就是符号表。
因此,整个 CC1 编译程序,进一步分解为下列程序模块。
模块 |
核心对象 |
程序 |
词汇分析 (Lexical Analysis) |
Scanner |
Scanner.c, Scanner.h |
语法分析 (Syntax Analysis) |
Parser |
Parser.c, Parser.h |
语意分析 (Semantic Analysis) |
Semantic |
Semantic.c, Semantic.h |
中间码产生 (Intermediate Code) |
PCode |
PCode.c, PCode.h |
汇编语言产生 (Code Generation) |
Generator |
Generator.c, Generator.h |
符号表 (Symbol Table) |
SymTable |
SymTable.c, SymTable.h |
Lua
- http://zh.wikipedia.org/wiki/Lua
Lua 的 BNF
chunk ::= {stat [`;´]} [laststat [`;´]]
block ::= chunk
stat ::= varlist `=´ explist |
functioncall |
do block end |
while exp do block end |
repeat block until exp |
if exp then block {elseif exp then block} [else block] end |
for Name `=´ exp `,´ exp [`,´ exp] do block end |
for namelist in explist do block end |
function funcname funcbody |
local function Name funcbody |
local namelist [`=´ explist]
laststat ::= return [explist] | break
funcname ::= Name {`.´ Name} [`:´ Name]
varlist ::= var {`,´ var}
var ::= Name | prefixexp `[´ exp `]´ | prefixexp `.´ Name
namelist ::= Name {`,´ Name}
explist ::= {exp `,´} exp
exp ::= nil | false | true | Number | String | `...´ | function |
prefixexp | tableconstructor | exp binop exp | unop exp
prefixexp ::= var | functioncall | `(´ exp `)´
functioncall ::= prefixexp args | prefixexp `:´ Name args
args ::= `(´ [explist] `)´ | tableconstructor | String
function ::= function funcbody
funcbody ::= `(´ [parlist] `)´ block end
parlist ::= namelist [`,´ `...´] | `...´
tableconstructor ::= `{´ [fieldlist] `}´
fieldlist ::= field {fieldsep field} [fieldsep]
field ::= `[´ exp `]´ `=´ exp | Name `=´ exp | exp
fieldsep ::= `,´ | `;´
binop ::= `+´ | `-´ | `*´ | `/´ | `^´ | `%´ | `..´ |
`<´ | `<=´ | `>´ | `>=´ | `==´ | `~=´ |
and | or
unop ::= `-´ | not | `#´
- Lua 5.1 Reference Manual — http://www.lua.org/manual/5.1/manual.html
- 最后有 Lua 的 BNF。
- Lua Interpreter in C — http://www.lua.org/source/5.1/lua.c.html
- Lua Compiler in Lua — http://lua-users.org/wiki/LuaCompilerInLua
- Lua Interpreter in Lua — http://lua-users.org/wiki/LuaInterpreterInLua
- http://luajit.org/ — The LuaJIT Project
CC1 编译程序的符号表
#ifndef SYMTABLE_H
#define SYMTABLE_H
#include "lib.h"
#include "HashTable.h"
#include "Tree.h"
// 型态 Type 有:函数、结构与指针与基本型态
// 基本 : int x;
// 指标 : int *px;
// 函数 : int total(int a[]) {...};
// 结构 : struct Person { ... };
typedef struct _Method {
char *name;
char *returnType;
Array *params;
} Method;
typedef struct _Struct {
char *name;
Array *fields;
} Struct;
typedef union _Type {
Method *pmethod;
Struct *pstruct;
char *pbtype;
} Type;
// 符号的值可能是 byte, int, float 或 pointer (包含 struct, method, type*)
typedef union _Value {
BYTE bvalue;
int ivalue;
float fvalue;
void *pvalue;
} Value;
// 变量符号: int x; Symbol(name=x, tag=VAR, type=int)
// 函数符号: int total(int a[]) {...}; Symbol(name=total, tag=METHOD, type=int)
// 结构符号: struct Person { ... }; Symbol(name=x, tag=ETYPE, type=int)
typedef struct _Symbol { // 符号记录
void *scope; // 所属领域
char *name; // 符号名称 (x, px, Person, total)
char *tag; // 符号标记 (变量定义 VAR 函数定义 METHOD、结构定义 STRUCT)
Type type; // 符号的形态
Value value; // 符号的值
} Symbol;
typedef HashTable SymTable;
Symbol *SymNew(void *scope, char *name, char *tag);
void SymFree(Symbol *s);
void TypeFree(Type *type);
SymTable *SymTableNew();
Symbol *SymTablePut(SymTable *table, Symbol *sym);
Symbol* SymTableGet(SymTable *table, void *scope, char *name);
void SymTableFree(SymTable *table);
void SymTableDebug(SymTable *table);
#endif
CC1 的词汇分析 (Scanner) 程序
档案:Scanner.h
#ifndef SCANNER_H
#define SCANNER_H
#include "lib.h"
typedef struct { // 扫描仪的对象结构
char *text; // 输入的程序 (text)
int len; // 程序的总长度
// 注意:以下的 xSave 都是在 ScannerStore() 与 ScannerRestore() 时使用的备份。
int i, iSave; // 目前词汇的位置
int line, lineSave; // 目前词汇的行号
int pos, posSave; // 目前词汇的起始点
char *tag, *tagSave; // 词汇的标记
char token[100], tokenSave[100]; // 目前的词汇
} Scanner;
void ScannerTest(char *fileName); // Scanner 词汇分析阶段的测试程序。
Scanner* ScannerNew(char *pText); // 建立新的词汇分析 Scanner 对象
void ScannerFree(Scanner *s); // 释放 Scanner 对象
void ScannerStore(Scanner *s); // 储存 Scanner 的目前状态
void ScannerRestore(Scanner *s); // 恢复 Scanner 的储存状态
BOOL ScannerIsNext(Scanner *s, char *pTags); // 检查下一个词汇是否符合 tag 标记。
void ScannerNext(Scanner *s); // 取得下一个词汇 (token)
char ch(Scanner *s); // 取得目前字符
void cnext(Scanner *s); // 前进到下一个字符
char *tokenToTag(char *token); // 对词汇 (token) 进行标记 (tag)
// 宣告 Token 变量,包含关键词 if, for, 运算符 ++, / 与 非终端项目 IF, FOR...
#define DEF(var, str) extern char var[];
#include "Token.h"
#undef DEF
#endif
档案:Scanner.c
#include <string.h>
#include "Scanner.h"
// 宣告关键词的字符串变量,像是 char kIF[]="if"; ...char EXP[]="EXP";...
#define DEF(var, str) char var[]=str;
#include "Token.h"
#undef DEF
// 宣告关键词数组, gTagList={...,"if", ...,"EXP", ... };
char *gTokenList[] = {
#define DEF(var, str) var,
#include "Token.h"
#undef DEF
};
// 功能:Scanner 词汇分析阶段的测试程序。
// 范例:ScannerTest("test.c1");
void ScannerTest(char *fileName) {
debug("======================ScannerTest()=========================\n");
char *text = fileToStr(fileName); // 读取整个程序文件,成为一个字符串 text
Scanner *s = ScannerNew(text); // 建立 Scanner 对象
while (TRUE) { // 不断扫描词汇,直到档案结束
ScannerNext(s); // 取得下一个词汇
debug("token=%-10s tag=%-10s line=%-4d pos=%-3d\n",
s->token, s->tag, s->line, s->pos);
if (s->tag == kEND) // 已经到程序结尾
break; // 结束扫描
}
ScannerFree(s); // 释放 Scanner 对象
strFree(text); // 释放字符串 text
memCheck(); // 检查内存
}
// 功能:建立新的词汇分析 Scanner 对象
// 范例:Scanner *s = ScannerNew(text);
Scanner* ScannerNew(char *pText) {
Scanner *s = ObjNew(Scanner, 1);
s->text = pText;
s->len = strlen(pText);
s->i = 0;
s->line = 1;
s->pos = 1;
// ScannerNext(s);
return s;
}
// 功能:释放 Scanner 对象
// 范例:ScannerFree(s);
void ScannerFree(Scanner *s) {
ObjFree(s);
}
// 功能:储存 Scanner 的目前状态
// 说明:剖析时若「偷看」后面几个 token,就必须使用 ScannerStore() 储存,然后呼叫
// ScannerNext() 偷看,之后再用 ScannerRestore() 恢复,以完成整个偷看过程。
// 范例:ScannerStore(s);
void ScannerStore(Scanner *s) {
s->iSave = s->i;
s->posSave = s->pos;
s->lineSave = s->line;
s->tagSave = s->tag;
strcpy(s->tokenSave, s->token);
}
// 功能:恢复 Scanner 的储存状态
// 范例:ScannerRestore(s);
void ScannerRestore(Scanner *s) {
s->i = s->iSave;
s->pos = s->posSave;
s->line = s->lineSave;
s->tag = s->tagSave;
strcpy(s->token, s->tokenSave);
}
// 功能:检查下一个词汇是否符合 tag 标记。
// 范例:if (ScannerIsNext(s, "+|-|*|/")) ScannerNext(s);
BOOL ScannerIsNext(Scanner *s, char *pTags) { // 检查下一个词汇的型态
char tTags[MAX_LEN+1];
sprintf(tTags, "|%s|", pTags);
if (strPartOf(s->tag, tTags))
return TRUE;
else
return FALSE;
}
// 功能:取得目前字符
// 范例:while (strMember(ch(s), DIGIT)) cnext(s);
char ch(Scanner *s) {
return s->text[s->i];
}
// 功能:前进到下一个字符
// 范例:while (strMember(ch(s), DIGIT)) cnext(s);
void cnext(Scanner *s) {
s->i++;s->pos++;
}
#define OP "+-*/%<=>!&|" // 运算符号字符集 (用来取得 +,-,*,/, ++, ...)
// 功能:Scanner 词汇分析阶段的测试程序。
// 范例:ScannerTest("test.c1");
void ScannerNext(Scanner *s) { // 扫描下一个词汇
while (strMember(ch(s), SPACE)) { // 忽略空白
if (ch(s)=='\n') {
s->line++;
s->pos = 1;
}
cnext(s);
}
if (s->i >= s->len) { // 如果超过程序结尾
s->tag = kEND; // 传回 tag = kEND
s->token[0] = '\0'; // 传回 token = 空字符串
return;
}
char c = ch(s); // 取得下一个字符
int begin = s->i; // 记住词汇开始点
if (c == '\"') { // 如果是 " 代表字符串开头
// 字符串常数 : string = ".."
cnext(s); // 跳过 "
while (ch(s) != '\"') cnext(s); // 一直读到下一个 " 符号为止。
cnext(s); // 跳过 "
} else if (strMember(c, OP)) { // 如果是OP(+-*/<=>!等符号)
// 运算符号 : OP = ++, --, <=, >=, ...
while (strMember(ch(s), OP)) cnext(s); // 一直读到不是OP为止
} else if (strMember(c, DIGIT)) { // 如果是数字
// 数字常数 : number = 312, 77568, ...
while (strMember(ch(s), DIGIT)) cnext(s); // 一直读到不是数字为止
// 浮点常数 : float = 3.14, ...
if (ch(s) == '.') cnext(s); // 取得小数点
while (strMember(ch(s), DIGIT)) cnext(s); // 取得小数部分
} else if (strMember(c, ALPHA)) { // 如果是英文字母
// 基本词汇 : token = int, sum, i, for, if, x1y2z, ....
while (strMember(ch(s), ALPHA) || strMember(ch(s), DIGIT))
cnext(s); // 一直读到不是英文字母 (或数字)为止
} else // 其他符号,都解读为单一字符
cnext(s); // 传回单一字符
// 字符串扫描完了,设定 token 为(begin…textIdx) 之间的子字符串
strSubstr(s->token, s->text, begin, (s->i) - begin);
// 设定 token 的标记 tag
s->tag = tokenToTag(s->token);
}
// 功能:Scanner 词汇分析阶段的测试程序。
// 范例:ScannerTest("test.c1");
char *tokenToTag(char *token) { // 判断并取得 token的型态
if (token[0] == '\"') // 如果以符号 " 开头,则
return CSTR; // 型态为 STRING
else if (strMember(token[0], DIGIT)) {// 如果是数字开头,则
if (strMember('.', token))
return CFLOAT;
else
return CINT;
} else { // 否则 (像是 +,-,*,/,>,<,….)
char *tag = NULL;
// 若是 keyword (包含 关键词 if, for 与 +, ->, {, ++ 等合法符号
// 则传回查表结果 (字符串指针)。
int i;
for (i=0; gTokenList[i] != kEND; i++) {
if (strEqual(token, gTokenList[i])) // 找到该 token,传回字符串指针。
return gTokenList[i];
}
if (strMember(token[0], ALPHA)) // 如果是英文字母开头
return ID; // 则型态为 ID
else
ERROR();
}
}
输入范例
int x=1, y=2;
struct Date {
int year, month, day;
}
struct Person {
char *name;
Date birthday;
}
int total(int* a) {
int s = 0;
for (int i=0; i<10; i++)
s = s+a[i];
return s;
}
char* getName(Person *p) {
return p->name;
}
int main() {
int b[10], a=3;
int t = total(b);
Person p;
p.birthday.year = 1990;
t = 3 + (5 * a);
return t;
}
测试程序 ScannerTest() 的执行结果
======================ScannerTest()===================
token=int tag=int line=1 pos=4
token=x tag=ID line=1 pos=6
token== tag== line=1 pos=7
token=1 tag=CINT line=1 pos=8
token=, tag=, line=1 pos=9
token=y tag=ID line=1 pos=11
token== tag== line=1 pos=12
token=2 tag=CINT line=1 pos=13
token=; tag=; line=1 pos=14
token=struct tag=struct line=3 pos=8
token=Date tag=ID line=3 pos=13
token={ tag={ line=3 pos=15
token=int tag=int line=4 pos=9
token=year tag=ID line=4 pos=14
token=, tag=, line=4 pos=15
token=month tag=ID line=4 pos=21
token=, tag=, line=4 pos=22
token=day tag=ID line=4 pos=26
token=; tag=; line=4 pos=27
token=} tag=} line=5 pos=3
token=struct tag=struct line=7 pos=8
token=Person tag=ID line=7 pos=15
token={ tag={ line=7 pos=17
token=char tag=char line=8 pos=7
token=* tag=* line=8 pos=9
token=name tag=ID line=8 pos=13
token=; tag=; line=8 pos=14
token=Date tag=ID line=9 pos=7
token=birthday tag=ID line=9 pos=16
token=; tag=; line=9 pos=17
token=} tag=} line=10 pos=3
token=int tag=int line=12 pos=5
token=total tag=ID line=12 pos=11
token=( tag=( line=12 pos=12
token=int tag=int line=12 pos=15
token=* tag=* line=12 pos=16
token=a tag=ID line=12 pos=18
token=) tag=) line=12 pos=19
token={ tag={ line=12 pos=21
token=int tag=int line=13 pos=6
token=s tag=ID line=13 pos=8
token== tag== line=13 pos=10
token=0 tag=CINT line=13 pos=12
token=; tag=; line=13 pos=13
token=for tag=for line=14 pos=6
token=( tag=( line=14 pos=8
token=int tag=int line=14 pos=11
token=i tag=ID line=14 pos=13
token== tag== line=14 pos=14
token=0 tag=CINT line=14 pos=15
token=; tag=; line=14 pos=16
token=i tag=ID line=14 pos=18
token=< tag=< line=14 pos=19
token=10 tag=CINT line=14 pos=21
token=; tag=; line=14 pos=22
token=i tag=ID line=14 pos=24
token=++ tag=++ line=14 pos=26
token=) tag=) line=14 pos=27
token=s tag=ID line=15 pos=5
token== tag== line=15 pos=7
token=s tag=ID line=15 pos=9
token=+ tag=+ line=15 pos=10
token=a tag=ID line=15 pos=11
token=[ tag=[ line=15 pos=12
token=i tag=ID line=15 pos=13
token=] tag=] line=15 pos=14
token=; tag=; line=15 pos=15
token=return tag=return line=16 pos=9
token=s tag=ID line=16 pos=11
token=; tag=; line=16 pos=12
token=} tag=} line=17 pos=3
token=char tag=char line=19 pos=6
token=* tag=* line=19 pos=7
token=getName tag=ID line=19 pos=15
token=( tag=( line=19 pos=16
token=Person tag=ID line=19 pos=22
token=* tag=* line=19 pos=24
token=p tag=ID line=19 pos=25
token=) tag=) line=19 pos=26
token={ tag={ line=19 pos=28
token=return tag=return line=20 pos=9
token=p tag=ID line=20 pos=11
token=-> tag=-> line=20 pos=13
token=name tag=ID line=20 pos=17
token=; tag=; line=20 pos=18
token=} tag=} line=21 pos=3
token=int tag=int line=23 pos=5
token=main tag=ID line=23 pos=10
token=( tag=( line=23 pos=11
token=) tag=) line=23 pos=12
token={ tag={ line=23 pos=14
token=int tag=int line=24 pos=6
token=b tag=ID line=24 pos=8
token=[ tag=[ line=24 pos=9
token=10 tag=CINT line=24 pos=11
token=] tag=] line=24 pos=12
token=, tag=, line=24 pos=13
token=a tag=ID line=24 pos=15
token== tag== line=24 pos=16
token=3 tag=CINT line=24 pos=17
token=; tag=; line=24 pos=18
token=int tag=int line=25 pos=6
token=t tag=ID line=25 pos=8
token== tag== line=25 pos=10
token=total tag=ID line=25 pos=16
token=( tag=( line=25 pos=17
token=b tag=ID line=25 pos=18
token=) tag=) line=25 pos=19
token=; tag=; line=25 pos=20
token=Person tag=ID line=26 pos=9
token=p tag=ID line=26 pos=11
token=; tag=; line=26 pos=12
token=p tag=ID line=27 pos=4
token=. tag=. line=27 pos=5
token=birthday tag=ID line=27 pos=13
token=. tag=. line=27 pos=14
token=year tag=ID line=27 pos=18
token== tag== line=27 pos=20
token=1990 tag=CINT line=27 pos=25
token=; tag=; line=27 pos=26
token=t tag=ID line=28 pos=4
token== tag== line=28 pos=6
token=3 tag=CINT line=28 pos=8
token=+ tag=+ line=28 pos=10
token=( tag=( line=28 pos=12
token=5 tag=CINT line=28 pos=13
token=* tag=* line=28 pos=15
token=a tag=ID line=28 pos=17
token=) tag=) line=28 pos=18
token=; tag=; line=28 pos=19
token=return tag=return line=29 pos=9
token=t tag=ID line=29 pos=11
token=; tag=; line=29 pos=12
token=} tag=} line=30 pos=3
token= tag=_?END?_ line=32 pos=3
Memory:newCount=438 freeCount=438
程序语言 C1 的语法规则
EBNF 语法
// =============== C1 语言的 EBNF 语法规则 ==================================
// PROG = (STRUCT | METHOD | DECL ; )*
// METHOD = TYPE ** ID(PARAM_LIST?) BLOCK
// STRUCT = struct ID { DECL_LIST ; }
// BLOCK = { BASE* }
// BASE = IF | FOR | WHILE | BLOCK | STMT ;
// IF = if (EXP) BASE (else BASE)?
// FOR = for (STMT ; EXP ; STMT) BASE
// WHILE = while (EXP) BASE
// STMT = return EXP | DECL | PATH (EXP_LIST) | PATH = EXP | PATH OP1
// VAR = ** ID ([ integer ])* (= EXP)?
// EXP = TERM (OP2 TERM)?
// TERM = ( EXP (OP2 EXP)? ) | CINT | CFLOAT | CSTR | PATH
// PATH = ATOM ((.|->) ATOM)*
// ATOM = ID (([ EXP ])* |( EXP_LIST? ))
// DECL = TYPE VAR_LIST
// PARAM = TYPE VAR
// VAR_LIST = VAR (, VAR)*
// EXP_LIST = EXP (, EXP)*
// DECL_LIST = DECL (; DECL)*
// PARAM_LIST = PARAM (, PARAM)*
// TYPE = (byte | char | int | float | ID) // 最后一个 ID 必须是 TYPE [STRUCT]
// ID = [A-Za-z_][0-9A-Za-z_]*
// CINT = [0-9]+
// CFLOAT = [0-9]+.[0-9]+
// CSTR = ".*"
// OP2 = +|-|/|*|%|&|&&|^|<<|>>|<|>|<=|>=|==|!=| 与 | , ||
// OP1 = ++ | --
C1 语言的剖析器 -- CC1
开放计算机计划 — 最新版本下载
- ss1v0.50.zip — 包含虚拟机 VM1, 组译器 AS1, 编译程序 CC1 (剖析器完成,符号表完成,程序代码产生修改中)
档案:Parser.h
// =============== C1 语言的 EBNF 语法规则 ==================================
// PROG = (STRUCT | METHOD | DECL ; )*
// METHOD = TYPE ** ID(PARAM_LIST?) BLOCK
// STRUCT = struct ID { DECL_LIST ; }
// BLOCK = { BASE* }
// BASE = IF | FOR | WHILE | BLOCK | STMT ;
// IF = if (EXP) BASE (else BASE)?
// FOR = for (STMT ; EXP ; STMT) BASE
// WHILE = while (EXP) BASE
// STMT = return EXP | DECL | PATH (EXP_LIST) | PATH = EXP | PATH OP1
// VAR = ** ID ([ integer ])* (= EXP)?
// EXP = TERM (OP2 TERM)?
// TERM = ( EXP (OP2 EXP)? ) | CINT | CFLOAT | CSTR | PATH
// PATH = ATOM ((.|->) ATOM)*
// ATOM = ID (([ EXP ])* |( EXP_LIST? ))
// DECL = TYPE VAR_LIST
// PARAM = TYPE VAR
// VAR_LIST = VAR (, VAR)*
// EXP_LIST = EXP (, EXP)*
// DECL_LIST = DECL (; DECL)*
// PARAM_LIST = PARAM (, PARAM)*
// TYPE = (byte | char | int | float | ID) // 最后一个 ID 必须是 TYPE [STRUCT]
// ID = [A-Za-z_][0-9A-Za-z_]*
// CINT = [0-9]+
// CFLOAT = [0-9]+.[0-9]+
// CSTR = ".*"
// OP2 = +|-|/|*|%|&|&&|^|<<|>>|<|>|<=|>=|==|!=| 与 | , ||
// OP1 = ++ | --
#ifndef PARSER_H
#define PARSER_H
#include "Scanner.h"
#include "Tree.h"
#include "Lib.h"
#include "Semantic.h"
typedef struct { // 剖析器的对象结构
Array *nodeStack; // 剖析过程用的节点 node 堆栈 (从树根到目前节点间的所有节点形成的堆栈)。
Array *blockStack; // 符号区块堆栈,变量 id 的区块范围,像是 PROG, STRUCT, METHOD, BLOCK 等。
Var decl; // 在 parseType 时用来记住型态的变量。
Scanner *scanner; // 词汇扫描仪 (Lexical Analysis)
SymTable *symTable; // 符号表
char spaces[MAX_LEN]; // 用来暂存空白字符串的变量。
} Parser;
Tree *parse(char *text, SymTable *symTable);// 剖析器的主程序
Parser *ParserNew(Scanner *scanner, SymTable *symTable); // 剖析器的建构函数
Tree *ParserParse(Parser *p, char *text); // 剖析器的剖析函数
void ParserFree(Parser *parser); // 释放内存
Tree* parseProg(Parser *p); // PROG = (STRUCT | METHOD | DECL ; )*
Tree* parseBase(Parser *p); // BASE = IF | FOR | WHILE | BLOCK | STMT ;
Tree* parseStruct(Parser *p); // STRUCT = struct ID { DECL_LIST ; }
Tree* parseMethod(Parser *p); // METHOD = TYPE ** ID(PARAM_LIST?) BLOCK
Tree* parseDecl(Parser *p); // DECL = TYPE VAR_LIST
Tree* parseIf(Parser *p); // IF = if (EXP) BASE (else BASE)?
Tree* parseFor(Parser *p); // FOR = for (STMT ; EXP ; STMT) BASE
Tree* parseWhile(Parser *p); // WHILE = while (EXP) BASE
Tree* parseStmt(Parser *p); // STMT = return EXP | DECL | PATH (EXP_LIST) | PATH = EXP | PATH OP1
Tree* parseBlock(Parser *p); // BLOCK = { BASE* }
Tree* parseVar(Parser *p); // VAR = ** ID ([ integer ])* (= EXP)?
Tree* parseExp(Parser *p); // EXP = TERM (OP2 TERM)?
Tree* parseTerm(Parser *p); // TERM = ( EXP (OP2 EXP)? ) | CINT | CFLOAT | CSTR | PATH
Tree* parsePath(Parser *p); // PATH = ATOM ((.|->) ATOM)*
Tree* parseAtom(Parser *p); // ATOM = ID (([ EXP ])* |( EXP_LIST? ))
Tree* parseDecl(Parser *p); // DECL = TYPE VAR_LIST
Tree* parseParam(Parser *p); // PARAM = TYPE VAR
Tree* parseVarList(Parser *p); // VAR_LIST = VAR (, VAR)*
Tree* parseExpList(Parser *p); // EXP_LIST = EXP (, EXP)*
Tree* parseDeclList(Parser *p); // DECL_LIST = DECL (; DECL)*
Tree* parseParamList(Parser *p);// PARAM_LIST = PARAM (, PARAM)*
Tree* parseType(Parser *p); // TYPE = (byte | char | int | float | ID)
Tree* parseId(Parser *p); // ID = [A-Za-z_][0-9A-Za-z_]*
BOOL isMethod(Parser *p); // 判断接下来是否为 METHOD 程序区块。
BOOL isDecl(Parser *p); // 判断接下来是否为 DECL 宣告语句
// push() : 功能:建立 tag 标记的非终端节点,并建立语意结构,然后推入堆栈中
// 范例:Tree *node = push(p, IF, SemIF);
#define push(p, tag, SemType) sem=ObjNew(SemType, 1);Tree *node=push1(p, tag);node->sem=sem;
Tree *push1(Parser *p, char* tag); // 建立标记为 tag 的新子树。
Tree *pop(Parser *p, char* tag); // 从堆栈中取出剖析完成的子树,并检查标记是否为 tag。
BOOL isNext(Parser *p, char *tags); // 检查下一个 token 的 tag 是否属于 tags 标记之一。
Tree *next(Parser *p, char *tags); // 取得下一个 token,并确认其 tag 为 tags 标记之一。
char *token(Tree *node); // 取得树叶节点 node 的 token。
void pushBlock(Parser *p, Symbol *sym); // 将区块符号推入堆栈
#define popBlock(p) ArrayPop(p->blockStack) // 从堆栈取出区块符号
#define peekBlock(p) ArrayPeek(p->blockStack) // 取得最上面的区块符号
// Token 的集合,用来检查是关键词,操作数,基本型态,或者只是变量 ID。
#define SET_KEYWORDS "|if|else|for|while|return|def|int|byte|char|float|struct|"
#define SET_OP1 "|++|--|"
#define SET_OP2 "|+|-|*|/|%|^|&|<<|>>|==|!=|<=|>=|<|>|&&||||"
#define SET_BTYPE "|int|byte|char|float|"
#endif
档案:Parser.c
#include "Parser.h"
// 功能:Parser 剖析阶段的测试程序。
// 范例:ParserTest("test.c1");
void ParserTest(char *fileName) {
debug("=======ParserTest()==========\n");
SymTable *symTable = SymTableNew(); // 建立符号表
char *text = fileToStr(fileName); // 读入 C1 语言程序代码,成为一字符串
Tree *tree = parse(text, symTable); // 剖析该程序代码,建立剖析树与符号表。
SymTableDebug(symTable); // 印出符号表。
TreeFree(tree); // 释放剖析树。
strFree(text); // 释放程序代码字符串
SymTableFree(symTable); // 释放符号表
memCheck(); // 检查内存
}
// 功能:剖析阶段的主程序
// 范例:Tree *tree = parse(text, symTable);
Tree *parse(char *text, SymTable *symTable) { // 剖析器的主要函数
Scanner *scanner = ScannerNew(text); // 建立扫描仪 (词汇分析用)
Parser *p=ParserNew(scanner, symTable); // 建立剖析器 (语法剖析用)
Tree *tree = ParserParse(p, text); // 剖析程序为语法树
ParserFree(p); // 释放颇析树
ScannerFree(scanner); // 释放扫描仪
return tree; // 传回剖析器
}
// 功能:建立新的剖析器 Parser 对象
// 范例:Parser *p = ParserNew(scanner, symTable);
Parser *ParserNew(Scanner *scanner, SymTable *symTable) {
Parser *p = ObjNew(Parser, 1); // 分配剖析器空间
p->nodeStack = ArrayNew(10); // 分配 nodeStack 堆栈空间
p->blockStack = ArrayNew(10); // 分配 blockStack 堆栈空间
p->scanner = scanner; // 设定扫瞄器
p->symTable = symTable; // 设定符号表
ScannerNext(scanner); // 本剖析器总是先取得下一个 token,以便 isNext() 进行判断。
return p;
}
// 功能:释放剖析器对象的内存
// 范例:ParserFree(p);
void ParserFree(Parser *p) {
ArrayFree(p->blockStack, (FuncPtr1) BlockFree); // 释放 blockStack 堆栈空间
ArrayFree(p->nodeStack, NULL); // 释放 nodeStack 堆栈空间
ObjFree(p); // 释放剖析器空间
}
// 功能:剖析整个程序代码 (text)。
// 范例:ParserParse(p, text);
Tree *ParserParse(Parser *p, char *text) { // 剖析对象的主函数
debug("======= parsing ========\n");
Tree *tree = parseProg(p); // 开始剖析整个程序 (PROG),并建立语法树 p->tree
if (p->nodeStack->count != 0) { // 如果剖析完成后堆栈是空的,那就是剖析成功
ERROR();// 否则就是剖析失败,有语法错误
}
return tree;
}
// 语法:PROG = (STRUCT | METHOD | DECL ; )*
// 功能:剖析 PROG 并建立语法树
// 范例:Tree *prog = parseProg(p);
Tree *parseProg(Parser *p) { // 剖析 PROG 规则
SemProg *sem=push(p, PROG, SemProg); // 建立 PROG 的语法树及语意结构
pushBlock(p, Global); // 推入全局区块
while (!isNext(p, kEND)) { // 剖析 BASE,直到程序结束或碰到 } 为止
if (isNext(p, "struct"))
parseStruct(p);
else { // 由于 METHOD 与 DECL 的开头都是 TYPE **ID ...,因此必须判断是哪一种情况。
if (isMethod(p)) { // 向前偷看后发现是 TYPE **ID(,所以是 Method
parseMethod(p);
} else { // 否则就必须是 DECL ;
parseDecl(p);
next(p, ";");
}
}
}
popBlock(p); // 取出全局区块
return pop(p, PROG); // 取出 PROG 的整棵语法树
}
// 语法:METHOD = TYPE **ID (PARAM_LIST?) BLOCK
// 功能:判断到底接下来是否为 METHOD,是的话传回 TRUE,否则传回 FALSE
// 由于 METHOD 与 DECL 的开头都是 TYPE **ID ...,因此必须判断是哪一种情况。
// 本函数会向前偷看,如果发现是 TYPE **ID(,那就应该是 Method。
// 范例:if (isMethod(p)) parseMethod(p);
BOOL isMethod(Parser *p) {
BOOL rzFlag = TRUE;
Scanner *s = p->scanner; // s=扫描仪
ScannerStore(s); // 储存扫描仪状态
if (isNext(p, "int|byte|char|float|ID")) // 偷看 TYPE
ScannerNext(s); // 略过 TYPE
else
rzFlag=FALSE;
while (isNext(p, "*")) ScannerNext(s); // 偷看并略过星号
if (isNext(p, ID)) // 偷看 ID
ScannerNext(s); // 略过 ID
else
rzFlag=FALSE;
if (!isNext(p, "(")) rzFlag=FALSE; // 如果接下来是 (,那么就应该是 Method。
ScannerRestore(s); // 恢复扫描仪状态。
return rzFlag;
}
// 语法:METHOD = TYPE **ID (PARAM_LIST?) BLOCK
// 功能:剖析 METHOD 并建立语法树
// 范例:Tree *method = parseMethod(p);
Tree* parseMethod(Parser *p) {
SemMethod *sem=push(p, METHOD, SemMethod); // 建立 METHOD 的语法树及语意结构
sem->type=parseType(p); // 剖析 TYPE
// 剖析 ** (n 个星号, n>=0)
int starCount = 0; // 星号数量的初始值
while (isNext(p, "*")) { // 如果下一个是星号
next(p, "*"); // 取得该星号
starCount ++; // 将星号数加一
}
sem->id = next(p, ID); // 剖析 ID
// 建立 ID 的符号记录 Symbol(id, METHOD)
char *id = token(sem->id); // 取得符号名称。
Symbol *sym = SymNew(Global, id, SymMethod); // 建立符号记录
Method *method = sym->typePtr; // 设定 method 结构。
method->ret.typeSym = p->decl.typeSym; // 设定传回符号
method->ret.starCount = p->decl.starCount; // 设定传回符号的星号个数。
SymTablePut(p->symTable, sym); // 将符号记录放入符号表中
pushBlock(p, sym); // 将 Method 符号推入区块堆栈
sem->symMethod = sym; // 设定语意结构 sem 的 symMethod 字段
// 剖析参数部分 (PARAM_LIST?)
next(p, "(");
if (!isNext(p, ")")) // 如果接下来不是 ),那就是有 PARAM_LIST
sem->paramList = parseParamList(p); // 剖析 PARAM_LIST
next(p, ")");
sem->block = parseBlock(p); // 剖析 BLOCK
popBlock(p);
return pop(p, METHOD); // 取出 METHOD 的语法树。
}
// 语法:STRUCT = struct ID { (DECL ;)* }
// 功能:剖析 STRUCT 并建立语法树
// 范例:Tree *s = parseStruct(p);
Tree* parseStruct(Parser *p) {
SemStruct *sem=push(p, STRUCT, SemStruct); // 建立 STRUCT 语法树
next(p, "struct"); // 剖析 struct
sem->id = next(p, ID); // 剖析 ID
// 建立 ID 的符号记录 Symbol(id, METHOD)
char *id = token(sem->id); // 取得符号名称。
Symbol *sym = SymNew(Global, id, SymStruct); // 建立符号 -- 结构。
SymTablePut(p->symTable, sym); // 放入符号表。
sem->symStruct = sym; // 设定语意结构 sem 的 symMethod 字段
pushBlock(p, sym); // 将 Struct 区块推入堆栈
// 剖析 { (DECL ;)* }
next(p, "{");
while (!isNext(p, "}")) {
parseDecl(p);
next(p, ";");
}
next(p, "}");
popBlock(p); // 从区块堆栈中取出 Struct 区块
return pop(p, STRUCT); // 取出 STRUCT 的语法树。
}
// 语法:BASE = IF | FOR | WHILE | BLOCK | STMT ;
// 功能:剖析 BASE 并建立 BASE 的语法树
// 范例:Tree *base = parseBase(p);
Tree* parseBase(Parser *p) { // 剖析 BASE 规则
SemBase *sem=push(p, BASE, SemBase); // 建立 BASE 的语法树及语意结构
if (isNext(p, "if")) // 如果下一个词汇是 if
parseIf(p); // 剖析 IF 程序段
else if (isNext(p, "for")) // 如果下一个词汇是 for
parseFor(p); // 剖析 FOR 程序段
else if (isNext(p, "while")) // 如果下一个词汇是 for
parseWhile(p); // 剖析 WHILE 程序段
else if (isNext(p, "{")) // 如果下一个词汇是 {
parseBlock(p); // 剖析 BLOCK 程序段
else { // 否则应该是 STMT ;
parseStmt(p); // 剖析 STMT 程序段
next(p, ";"); // 取得分号 ;
}
return pop(p, BASE); // 取出 BASE 的剖析树
}
// 语法:BLOCK = { BASE* }
// 功能:剖析 BLOCK 并建立语法树
// 范例:Tree *block = parseBlock(p);
Tree* parseBlock(Parser *p) {
SemBlock *sem=push(p, BLOCK, SemBlock); // 建立 BLOCK 的语法树及语意结构
Symbol *pblock = peekBlock(p); // 取得父区块
Symbol *sym = SymNew(pblock, "", SymBlock); // 建立区块符号
Block *block = sym->typePtr; // 设定 block 结构。
SymTablePut(p->symTable, sym); // 将本区块加入到符号表中
sem->symBlock = sym; // 设定本节点的语意结构 symBlock 为本区块
pushBlock(p, sym); // 将符号推入区块堆栈
next(p, "{"); // 剖析 { BASE* }
while (!isNext(p, "}"))
parseBase(p);
next(p, "}");
popBlock(p); // 从区块堆栈中取出 Block 区块
return pop(p, BLOCK); // 取出 BLOCK 的语法树。
}
// 语法:FOR = for (STMT ; EXP ; STMT) BASE
// 功能:剖析 FOR 并建立语法树
// 范例:Tree *f = parseFor(p);
Tree* parseFor(Parser *p) {
SemFor *sem=push(p, FOR, SemFor); // 建立 FOR 的语法树及语意结构
next(p, "for"); // 取得 for
next(p, "("); // 取得 (
sem->stmt1 = parseStmt(p); // 剖析 STMT
next(p, ";"); // 取得 ;
sem->exp = parseExp(p); // 剖析 EXP
next(p, ";"); // 取得 ;
sem->stmt2 = parseStmt(p); // 剖析 STMT
next(p, ")"); // 取得 )
parseBase(p); // 剖析 BASE
return pop(p, FOR); // 取出 FOR 的语法树。
}
// 语法:IF = if (EXP) BASE (else BASE)?
// 功能:剖析 IF 并建立语法树
// 范例:Tree *f = parseIf(p);
Tree* parseIf(Parser *p) {
SemIf *sem=push(p, IF, SemIf); // 建立 IF 的语法树及语意结构
next(p, "if"); // 取得 if
next(p, "("); // 取得 (
sem->exp = parseExp(p); // 剖析 EXP
next(p, ")"); // 取得 )
sem->base1 = parseBase(p); // 剖析 BASE
if (isNext(p, "else")) { // 如果下一个是 else
next(p, "else"); // 取得 else
sem->base2 = parseBase(p); // 剖析下一个 BASE
}
return pop(p, IF); // 取出 IF 的语法树。
}
// 语法:WHILE = while (EXP) BASE
// 功能:剖析 WHILE 并建立语法树
// 范例:Tree *w = parseWhile(p);
Tree* parseWhile(Parser *p) {
SemWhile *sem=push(p, WHILE, SemWhile);// 建立 WHILE 的语法树及语意结构
next(p, "while"); // 取得 while
next(p, "("); // 取得 (
sem->exp = parseExp(p); // 剖析 EXP
next(p, ")"); // 取得 )
sem->base = parseBase(p); // 剖析 BASE
return pop(p, WHILE); // 取出 WHILE 的语法树。
}
// 语法:STMT = return EXP | DECL | PATH (EXP_LIST) | PATH = EXP | PATH OP1
// 功能:剖析 STMT 并建立语法树
// 范例:Tree *stmt = parseStmt(p);
Tree* parseStmt(Parser *p) {
SemStmt *sem=push(p, STMT, SemStmt);// 建立 STMT 的语法树及语意结构
if (isNext(p, "return")) { // 如果下一个是 return,就剖析 return EXP
next(p, "return");
sem->exp = parseExp(p);
} else if (isDecl(p)) { // 如果是 DECL
sem->decl = parseDecl(p); // 剖析 DECL
} else { // 否则下一个必须是 PATH
sem->path = parsePath(p); // 剖析 PATH
if (isNext(p, "(")) { // 下一个是 (,代表是 PATH (EXP_LIST) 的情况
next(p, "(");
sem->expList = parseExpList(p);
next(p, ")");
} else if (isNext(p, "=")) { // 下一个是 =,代表是 PATH = EXP 的情况
next(p, "=");
sem->exp = parseExp(p);
} else if (isNext(p, SET_OP1)) { // 下一个是OP1,代表是 PATH OP1 的情况
next(p, SET_OP1);
} else
ERROR();
}
return pop(p, STMT); // 取出 STMT 的语法树。
}
// 语法:PATH = ATOM ((.|->) ATOM)*
// 功能:剖析 PATH 并建立语法树
// 范例:Tree *path = parsePath(p);
Tree* parsePath(Parser *p) {
SemPath *sem=push(p, PATH, SemPath);// 建立 PATH 的语法树及语意结构
parseAtom(p); // 剖析 DECL
while (isNext(p, ".|->")) { // 不断取得 (.|->) ATOM
next(p, ".|->");
parseAtom(p);
}
return pop(p, PATH); // 取出 PATH 的语法树。
}
// 语法:ATOM = ID (([ EXP ])* |( EXP_LIST? ))
// 功能:剖析 ATOM 并建立语法树
// 范例:Tree *atom = parseAtom(p);
Tree* parseAtom(Parser *p) {
SemAtom *sem=push(p, ATOM, SemAtom); // 建立 ATOM 的语法树及语意结构
sem->id = next(p, ID); // 取得 ID
sem->subTag = ID; // 设定子标签 (ID, CALL 或 ARRAY_MEMBER),让语义分析与程序产生时使用
if (isNext(p, "(")) { // 如果接下来是 (,则应该是函数呼叫 ID ( EXP_LIST? )
next(p, "(");
if (!isNext(p, ")"))
sem->expList = parseExpList(p);
next(p, ")");
sem->subTag = CALL;
} else if (isNext(p, "[")) { // 如果接下来是 [,则应该是数组宣告 ID ([ EXP ])*
sem->subTag = ARRAY_MEMBER;
while (isNext(p, "[")) {
next(p, "[");
Tree *exp = parseExp(p);
next(p, "]");
}
}
return pop(p, ATOM); // 取出 ATOM 的语法树。
}
// 语法:PARAM = TYPE VAR
// 功能:剖析 PARAM 并建立语法树
// 范例:Tree *param = parseParam(p);
Tree* parseParam(Parser *p) {
SemParam *sem = push(p, PARAM, SemParam);// 建立 PARAM 的语法树及语意结构
sem->type = parseType(p); // 剖析 TYPE
sem->var = parseVar(p); // 剖析 VAR
return pop(p, PARAM); // 取出 PARAM 的语法树。
}
// 语法:DECL = TYPE VAR_LIST
// 功能:判断到底接下来是否为 DECL,是的话传回 TRUE,否则传回 FALSE
// 本函数会向前偷看,如果发现是 (int|byte|char|float|ID)** ID,那就是 DECL
// 范例:if (isDecl(p)) parseDecl(p);
BOOL isDecl(Parser *p) {
BOOL rzFlag = TRUE;
Scanner *s = p->scanner; // s=扫描仪
ScannerStore(s); // 储存扫描仪状态
if (isNext(p, "int|byte|char|float|ID"))// 偷看 TYPE
ScannerNext(s); // 略过 TYPE
else
rzFlag=FALSE;
while (isNext(p, "*")) ScannerNext(s); // 偷看并略过星号
if (!isNext(p, ID)) rzFlag=FALSE; // 偷看 ID
ScannerRestore(s); // 恢复扫描仪状态。
return rzFlag;
}
// 语法:DECL = TYPE VAR_LIST
// 功能:剖析 PROG 并建立语法树
// 范例:Tree *decl = parseDecl(p);
Tree* parseDecl(Parser *p) {
SemDecl *sem = push(p, DECL, SemDecl);// 建立 DECL 的语法树及语意结构
sem->type = parseType(p); // 剖析 TYPE
sem->varList = parseVarList(p); // 剖析 VAR_LIST
return pop(p, DECL); // 取出 DECL 的语法树。
}
// 语法:TYPE = (int | byte | char | float | ID) // ID is STRUCT_TYPE
// 功能:剖析 TYPE 并建立语法树
// 范例:Tree *type = parseType(p);
Tree* parseType(Parser *p) {
SemType *sem=push(p, TYPE, SemType);// 建立 TYPE 的语法树及语意结构
Tree *type = next(p, "int|byte|char|float|ID"); // 取得 (int | byte | char | float | ID)
char *typeName = token(type); // 取得型态名称
p->decl.typeSym = SymTableGet(p->symTable, Global, typeName); // 从符号表中查出该型态的符号
ASSERT(p->decl.typeSym != NULL);
return pop(p, TYPE); // 取出 TYPE 的语法树。
}
// 语法:VAR = ** ID ([ CINT ])* (= EXP)?
// 功能:剖析 VAR 并建立语法树
// 范例:Tree *var = parseVar(p);
Tree* parseVar(Parser *p) {
SemVar *sem = push(p, VAR, SemVar); // 建立 VAR 的语法树及语意结构
int starCount = 0; // 星号数量初始值为 0
while (isNext(p, "*")) { // 剖析 **
next(p, "*"); // 取得星号
starCount ++; // 计算星号数量
}
sem->id = next(p, ID); // 剖析 ID
// 建立 ID 的符号记录 Symbol(id, SymVar)
Symbol *pblock = peekBlock(p); // 取得父区块符号
char *id = token(sem->id); // 取得变量名称
Symbol *sym = SymNew(pblock, id, SymVar); // 建立变量符号
Var *var = sym->typePtr; // 取出变量结构
var->starCount = starCount; // 设定变量结构中的星号数量
var->typeSym = p->decl.typeSym; // 设定变量结构中的符号
var->dimCount = 0; // 设定变量结构中的数组维度
SymTablePut(p->symTable, sym); // 将变量加入符号表中
while (isNext(p, "[")) { // 剖析 ([ CINT ])*
next(p, "[");
Tree *cint = next(p, "CINT");
ASSERT(var->dimCount<DIM_MAX);
var->dim[var->dimCount++] = atoi(token(cint));
next(p, "]");
}
if (pblock->symType == SymStruct) { // 如果父区块是 Struct,那此 VAR 就是字段宣告。
Struct *stru = pblock->typePtr;
ArrayAdd(stru->fields, sym); // 将变量加入 Struct 的字段 fields 中。
} else if (pblock->symType == SymMethod) { // 如果父区块是 Method,那此 VAR 就是参数宣告。
Method *method = pblock->typePtr;
ArrayAdd(method->params, sym); // 将变数加入 Method 的参数 params 中。
} else if (pblock->symType == SymBlock) { // 如果父区块是 Block,那此 VAR 就是局部变量。
Block *block = pblock->typePtr;
ArrayAdd(block->vars, sym);// 将变数加入 Block 的局部变量 vars 中。
}
if (isNext(p, "=")) { // 剖析 (= EXP)?
next(p, "=");
sem->exp = parseExp(p);
}
return pop(p, VAR); // 取出 VAR 的语法树。
}
// 语法:EXP = TERM (OP2 TERM)?
// 功能:剖析 EXP 并建立语法树
// 范例:Tree *exp = parseExp(p);
Tree* parseExp(Parser *p) {
SemExp *sem = push(p, EXP, SemExp);// 建立 EXP 的语法树及语意结构
sem->term1 = parseTerm(p); // 剖析 TERM
if (isNext(p, SET_OP2)) { // 如果接下来是 OP2 ,则剖析 (OP2 TERM)?
sem->op = next(p, SET_OP2);
sem->term2 = parseTerm(p);
}
return pop(p, EXP); // 取出 EXP 的语法树。
}
// 语法:TERM = ( EXP (OP2 EXP)? ) | CINT | CFLOAT | CSTR | PATH
// 功能:剖析 TERM 并建立语法树
// 范例:Tree *term = parseTerm(p);
Tree* parseTerm(Parser *p) {
SemTerm *sem = push(p, TERM, SemTerm);// 建立 TERM 的语法树及语意结构
if (isNext(p, "(")) { // 如果下一个是 (,那就是 ( EXP (OP2 EXP)? ) 的情况
next(p, "(");
sem->exp1 = parseExp(p);
if (!isNext(p, ")")) { // 看看是否有 (OP2 EXP)
next(p, SET_OP2);
sem->exp2 = parseExp(p);
}
next(p, ")");
} else if (isNext(p, "CINT|CFLOAT|CSTR")) { // 如果是 CINT, CFLOAT 或 CSTR
next(p, "CINT|CFLOAT|CSTR"); // 取得 CINT, CFLOAT 或 CSTR
} else
parsePath(p); // 否则应该是 PATH,剖析之
return pop(p, TERM); // 取出 TERM 的语法树。
}
// 语法:VAR_LIST = VAR (, VAR)*
// 功能:剖析 VarList 并建立语法树
// 范例:Tree *varList = parseVarList(p);
Tree* parseVarList(Parser *p) {
SemVarList *sem = push(p, VAR_LIST, SemVarList);// 建立 VAR_LIST 的语法树及语意结构
parseVar(p); // 剖析 VAR
while (isNext(p, ",")) { // 剖析 (,VAR)*
next(p, ",");
parseVar(p);
}
return pop(p, VAR_LIST); // 取出 VAR_LIST 的语法树。
}
// 语法:EXP_LIST = EXP (, EXP)*
// 功能:剖析 EXP_LIST 并建立语法树
// 范例:Tree *expList = parseExpList(p);
Tree* parseExpList(Parser *p) {
SemExpList *sem = push(p, EXP_LIST, SemExpList);// 建立 EXP_LIST 的语法树及语意结构
parseExp(p); // 剖析 EXP
while (isNext(p, ",")) { // 剖析 (, EXP)*
next(p, ",");
parseExp(p);
}
return pop(p, EXP_LIST); // 取出 EXP_LIST 的语法树。
}
// 语法:DECL_LIST = DECL (; DECL)*
// 功能:剖析 DECL_LIST 并建立语法树
// 范例:Tree *declList = parseDeclList(p);
Tree* parseDeclList(Parser *p) {
SemDeclList *sem=push(p, DECL_LIST, SemDeclList);// 建立 DECL_LIST 的语法树及语意结构
parseDecl(p); // 剖析 DECL
while (isNext(p, ";")) { // 剖析 (; DECL)*
next(p, ";");
parseDecl(p);
}
return pop(p, DECL_LIST); // 取出 DECL_LIST 的语法树。
}
// 语法:PARAM_LIST = PARAM (, PARAM)*
// 功能:剖析 PARAM_LIST 并建立语法树
// 范例:Tree *paramList = parseParamList(p);
Tree* parseParamList(Parser *p) {
SemParamList *sem=push(p, PARAM_LIST, SemParamList);// 建立 PARAM_LIST 的语法树及语意结构
parseParam(p); // 剖析 PARAM
while (isNext(p, ";")) { // 剖析 (, PARAM)*
next(p, ";");
parseParam(p);
}
return pop(p, PARAM_LIST); // 取出 PARAM_LIST 的语法树。
}
// ========================== 基本函数 ====================================
// 功能:取得 p->nodeStack->count 个空白, 以便印出剖析树时能有阶层式的排版。
// 范例:debug("%s KEY:%s\n", level(p), s->tag);
char* level(Parser *p) {
return strFill(p->spaces, ' ', p->nodeStack->count);
}
// 功能:判断下一个 token 的标记是否为 tags 其中之一
// 范例:if (isNext(p, "struct")) parseStruct(p);
BOOL isNext(Parser *p, char *tags) { // 检查下一个词汇的型态
Scanner *s = p->scanner;
char tTags[MAX_LEN+1];
sprintf(tTags, "|%s|", tags);
if (strPartOf(s->tag, tTags))
return TRUE;
else
return FALSE;
}
// 功能:取得下一个 token (标记必须为 tag 其中之一),然后挂到剖析树上
// 范例:Tree *node = next(p, "CINT|CFLOAT|CSTR");
Tree *next(Parser *p, char *tags) { // 检查下一个词汇的型态
Scanner *s = p->scanner;
if (isNext(p, tags)) { // 如果是pTypes型态之一
Tree *child = TreeNew(s->tag);
child->sem = strNew(s->token); // 建立词汇节点(token,type)
Tree *parentTree = ArrayPeek(p->nodeStack); // 取得父节点,
TreeAddChild(parentTree, child); // 加入父节点成为子树
if (strEqual(s->tag, s->token))
debug("%s KEY:%s\n", level(p), s->tag);
else
debug("%s %s:%s\n", level(p), s->tag, s->token);
ScannerNext(s);
return child; // 传回该词汇
} else { // 否则(下一个节点型态错误)
debug("next():token=%s, tag=%s is not in tag(%s)\n", s->token, s->tag, tags); // 印出错误讯息
ERROR();
return NULL;
}
}
// 功能:建立 tag 标记的非终端节点,并且推入堆栈中
// 范例:Tree *node = push1(p, IF);
Tree* push1(Parser *p, char* tag) { // 建立 pType 型态的子树,推入堆栈中
debug("%s+%s\n", level(p), tag);
Tree *node = TreeNew(tag);
ArrayPush(p->nodeStack, node);
return node;
}
// 功能:取出 tag 标记的非终端节点,然后挂到剖析树上
// 范例:Tree *node = pop(p, IF);
Tree* pop(Parser *p, char* tag) { // 取出 pTag 标记的子树
Tree *tree = ArrayPop(p->nodeStack); // 取得堆栈最上层的子树
debug("%s-%s\n", level(p), tree->tag); // 印出以便观察
if (strcmp(tree->tag, tag)!=0) { // 如果型态不符合
debug("pop(%s):should be %s\n",tree->tag, tag); // 印出错误讯息
ERROR();
}
if (p->nodeStack->count > 0) { // 如果堆栈不是空的
Tree *parentTree = ArrayPeek(p->nodeStack); // 取出上一层剖析树
TreeAddChild(parentTree, tree); // 将建构完成的剖析树挂到树上,成为子树
}
return tree;
}
// 功能:取得树叶节点中的词汇 (token)
// 范例:char *token = token(node);
char *token(Tree *node) {
return (char*) node->sem;
}
// 功能:将区块符号 sym 推入区块堆栈中
// 范例:pushBlock(p, sym);
void pushBlock(Parser *p, Symbol *sym) {
ArrayPush(p->blockStack, sym);
}
测试输入程序:被剖析者 — test.c1
int x=1, y=2;
struct Date {
int year, month, day;
}
struct Person {
char *name;
Date birthday;
}
int total(int* a) {
int s = 0;
for (int i=0; i<10; i++)
s = s+a[i];
return s;
}
char* getName(Person *p) {
return p->name;
}
int main() {
int b[10], a=3;
int t = total(b);
Person p;
p.birthday.year = 1990;
t = 3 + (5 * a);
return t;
}
剖析器的输出结果
======= parsing ========
+PROG
+DECL
+TYPE
KEY:int
-TYPE
+VAR_LIST
+VAR
ID:x
V x 0 003E2558 0040A340 int:*0:[0]
KEY:=
+EXP
+TERM
CINT:1
-TERM
-EXP
-VAR
KEY:,
+VAR
ID:y
V y 0 003E6590 0040A340 int:*0:[0]
KEY:=
+EXP
+TERM
CINT:2
-TERM
-EXP
-VAR
-VAR_LIST
-DECL
KEY:;
+STRUCT
KEY:struct
ID:Date
S Date 0 003E6830 0040A340
KEY:{
+DECL
+TYPE
KEY:int
-TYPE
+VAR_LIST
+VAR
ID:year
V year 0 003E6A80 003E6830 int:*0:[0]
-VAR
KEY:,
+VAR
ID:month
V month 0 003E6BD8 003E6830 int:*0:[0]
-VAR
KEY:,
+VAR
ID:day
V day 0 003E6D18 003E6830 int:*0:[0]
-VAR
-VAR_LIST
-DECL
KEY:;
KEY:}
-STRUCT
+STRUCT
KEY:struct
ID:Person
S Person 0 003E6EB8 0040A340
KEY:{
+DECL
+TYPE
KEY:char
-TYPE
+VAR_LIST
+VAR
KEY:*
ID:name
V name 0 003E7148 003E6EB8 char:*1:[0]
-VAR
-VAR_LIST
-DECL
KEY:;
+DECL
+TYPE
ID:Date
-TYPE
+VAR_LIST
+VAR
ID:birthday
V birthday 0 003E7398 003E6EB8 Date:*0:[0]
-VAR
-VAR_LIST
-DECL
KEY:;
KEY:}
-STRUCT
+METHOD
+TYPE
KEY:int
-TYPE
ID:total
M total 0 003E75F8 0040A340
KEY:(
+PARAM_LIST
+PARAM
+TYPE
KEY:int
-TYPE
+VAR
KEY:*
ID:a
V a 0 003E78A8 003E75F8 int:*1:[0]
-VAR
-PARAM
-PARAM_LIST
KEY:)
+BLOCK
B 0 003E79B0 003E75F8
KEY:{
+BASE
+STMT
+DECL
+TYPE
KEY:int
-TYPE
+VAR_LIST
+VAR
ID:s
V s 0 003E7C60 003E79B0 int:*0:[0]
KEY:=
+EXP
+TERM
CINT:0
-TERM
-EXP
-VAR
-VAR_LIST
-DECL
-STMT
KEY:;
-BASE
+BASE
+FOR
KEY:for
KEY:(
+STMT
+DECL
+TYPE
KEY:int
-TYPE
+VAR_LIST
+VAR
ID:i
V i 0 003E8128 003E79B0 int:*0:[0]
KEY:=
+EXP
+TERM
CINT:0
-TERM
-EXP
-VAR
-VAR_LIST
-DECL
-STMT
KEY:;
+EXP
+TERM
+PATH
+ATOM
ID:i
-ATOM
-PATH
-TERM
KEY:<
+TERM
CINT:10
-TERM
-EXP
KEY:;
+STMT
+PATH
+ATOM
ID:i
-ATOM
-PATH
KEY:++
-STMT
KEY:)
+BASE
+STMT
+PATH
+ATOM
ID:s
-ATOM
-PATH
KEY:=
+EXP
+TERM
+PATH
+ATOM
ID:s
-ATOM
-PATH
-TERM
KEY:+
+TERM
+PATH
+ATOM
ID:a
KEY:[
+EXP
+TERM
+PATH
+ATOM
ID:i
-ATOM
-PATH
-TERM
-EXP
KEY:]
-ATOM
-PATH
-TERM
-EXP
-STMT
KEY:;
-BASE
-FOR
-BASE
+BASE
+STMT
KEY:return
+EXP
+TERM
+PATH
+ATOM
ID:s
-ATOM
-PATH
-TERM
-EXP
-STMT
KEY:;
-BASE
KEY:}
-BLOCK
-METHOD
+METHOD
+TYPE
KEY:char
-TYPE
KEY:*
ID:getName
M getName 0 003E9270 0040A340
KEY:(
+PARAM_LIST
+PARAM
+TYPE
ID:Person
-TYPE
+VAR
KEY:*
ID:p
V p 0 003E9518 003E9270 Person:*1:[0]
-VAR
-PARAM
-PARAM_LIST
KEY:)
+BLOCK
B 0 003E9608 003E9270
KEY:{
+BASE
+STMT
KEY:return
+EXP
+TERM
+PATH
+ATOM
ID:p
-ATOM
KEY:->
+ATOM
ID:name
-ATOM
-PATH
-TERM
-EXP
-STMT
KEY:;
-BASE
KEY:}
-BLOCK
-METHOD
+METHOD
+TYPE
KEY:int
-TYPE
ID:main
M main 0 003E9B70 0040A340
KEY:(
KEY:)
+BLOCK
B 0 003E9CD8 003E9B70
KEY:{
+BASE
+STMT
+DECL
+TYPE
KEY:int
-TYPE
+VAR_LIST
+VAR
ID:b
V b 0 003E9F88 003E9CD8 int:*0:[0]
KEY:[
CINT:10
KEY:]
-VAR
KEY:,
+VAR
ID:a
V a 0 003EA170 003E9CD8 int:*0:[0]
KEY:=
+EXP
+TERM
CINT:3
-TERM
-EXP
-VAR
-VAR_LIST
-DECL
-STMT
KEY:;
-BASE
+BASE
+STMT
+DECL
+TYPE
KEY:int
-TYPE
+VAR_LIST
+VAR
ID:t
V t 0 003EA560 003E9CD8 int:*0:[0]
KEY:=
+EXP
+TERM
+PATH
+ATOM
ID:total
KEY:(
+EXP_LIST
+EXP
+TERM
+PATH
+ATOM
ID:b
-ATOM
-PATH
-TERM
-EXP
-EXP_LIST
KEY:)
-ATOM
-PATH
-TERM
-EXP
-VAR
-VAR_LIST
-DECL
-STMT
KEY:;
-BASE
+BASE
+STMT
+DECL
+TYPE
ID:Person
-TYPE
+VAR_LIST
+VAR
ID:p
V p 0 003EAC48 003E9CD8 Person:*0:[0]
-VAR
-VAR_LIST
-DECL
-STMT
KEY:;
-BASE
+BASE
+STMT
+PATH
+ATOM
ID:p
-ATOM
KEY:.
+ATOM
ID:birthday
-ATOM
KEY:.
+ATOM
ID:year
-ATOM
-PATH
KEY:=
+EXP
+TERM
CINT:1990
-TERM
-EXP
-STMT
KEY:;
-BASE
+BASE
+STMT
+PATH
+ATOM
ID:t
-ATOM
-PATH
KEY:=
+EXP
+TERM
CINT:3
-TERM
KEY:+
+TERM
KEY:(
+EXP
+TERM
CINT:5
-TERM
KEY:*
+TERM
+PATH
+ATOM
ID:a
-ATOM
-PATH
-TERM
-EXP
KEY:)
-TERM
-EXP
-STMT
KEY:;
-BASE
+BASE
+STMT
KEY:return
+EXP
+TERM
+PATH
+ATOM
ID:t
-ATOM
-PATH
-TERM
-EXP
-STMT
KEY:;
-BASE
KEY:}
-BLOCK
-METHOD
-PROG
type name size this scope varType
V i 0 003E8128 003E79B0 int:*0:[0]
M main 0 003E9B70 0040A340
V month 0 003E6BD8 003E6830 int:*0:[0]
V name 0 003E7148 003E6EB8 char:*1:[0]
M total 0 003E75F8 0040A340
V x 0 003E2558 0040A340 int:*0:[0]
V s 0 003E7C60 003E79B0 int:*0:[0]
V y 0 003E6590 0040A340 int:*0:[0]
B 0 003E9CD8 003E9B70
V a 0 003EA170 003E9CD8 int:*0:[0]
V b 0 003E9F88 003E9CD8 int:*0:[1]
S Person 0 003E6EB8 0040A340
T int 4 003E5EB0 0040A340
V a 0 003E78A8 003E75F8 int:*1:[0]
V p 0 003EAC48 003E9CD8 Person:*0:[0]
T char 1 003E57E0 0040A340
V t 0 003EA560 003E9CD8 int:*0:[0]
T float 4 003E5778 0040A340
B 0 003E79B0 003E75F8
V day 0 003E6D18 003E6830 int:*0:[0]
M getName 0 003E9270 0040A340
V birthday 0 003E7398 003E6EB8 Date:*0:[0]
V p 0 003E9518 003E9270 Person:*1:[0]
V year 0 003E6A80 003E6830 int:*0:[0]
S Date 0 003E6830 0040A340
B 0 003E9608 003E9270
Memory:newCount=2090 freeCount=2090
C1 程序语言
范例一
int x=1, y=2;
struct Date {
int year, month, day;
}
struct Person {
char *name;
Date birthday;
}
int total(int* a) {
int s = 0;
for (int i=0; i<10; i++)
s = s+a[i];
return s;
}
char* getName(Person *p) {
return p->name;
}
int main() {
int b[10], a=3;
int t = total(b);
Person p;
p.birthday.year = 1990;
t = 3 + (5 * a);
return t;
}
参考链接:
http://ccckmit.wikidot.com/ocs:compiler
这篇关于CPU0 处理器的架构及应用的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-26MATLAB 中 A(7)=[];什么意思?-icode9专业技术文章分享
- 2024-11-26UniApp 中如何实现使用输入法时保持页面列表不动的效果?-icode9专业技术文章分享
- 2024-11-26在 UniApp 中怎么实现输入法弹出时禁止页面向上滚动?-icode9专业技术文章分享
- 2024-11-26WebSocket是什么,怎么使用?-icode9专业技术文章分享
- 2024-11-26页面有多个ref 要动态传入怎么实现?-icode9专业技术文章分享
- 2024-11-26在 UniApp 中实现一个底部输入框的常见方法有哪些?-icode9专业技术文章分享
- 2024-11-26RocketMQ入门指南:搭建与使用全流程详解
- 2024-11-26RocketMQ入门教程:轻松搭建与使用指南
- 2024-11-26手写RocketMQ:从入门到实践的简单教程
- 2024-11-25【机器学习(二)】分类和回归任务-决策树(Decision Tree,DT)算法-Sentosa_DSML社区版