编译原理compiler2_一个微小编译器.ppt

第二章一个微小编译器 2 1Micro语言描述2 2Micro语言的词法分析2 3Micro语言的语法分析2 4Micro语言的语义分析2 5Micro语言的目标代码 第二章一个微小编译器 2 1Micro语言描述Micro语言 称Micro Pascal语言的子集 beginvarx1 real varz1 real x1 0 5 z1 x1 56 write z1 2 3 read x1 end Micro的有用单词的种类 以字母开头 保留字 begin end var read write int real标识符 字母 数字串以数字开头 整常数 数字开头的数字串实常数 整数 整数符号词 控制词 enter 2 2Micro语言的词法分析 单词的分析 特点 不依赖于语法分析 只依赖于单词的文法定义 任务 程序的字符串序列Token序列 单词的内部表示 保留字 begin end var read write int real标识符 id 标识符 整常数 intC 整常数 实常数 reaC 实常数 符号词 plus sub mult div Lparen Rparen colon assig semi line stop enter 输入 输出 例 beginvarx1 real varz1 real x1 0 5 z1 x1 56 write z1 2 3 read x1 end 程序的字符串序列Token序列 3 Micro语言的词法分析程序 Procedurescanner beginwhile Eofdo Noblank ch casechof A Z a z Identifier name casenameof begin GenToken begin end GenToken end var GenToken var int GenToken int real GenToken real read GenToken read write GenToken write otherGenToken id name end Noblank ch 跳过空格符串将第一个非空格字符读到ch中 删除空格符 例 beginvarx1 real varz1 real x1 0 5 z1 x1 56 write z1 2 3 read x1 end 0 9 Constant class C GenToken Class C GenToken Lparen Read ch GenToken Rparen Read ch GenToken plus Read ch GenToken mult Read ch GenToken semi Read ch Read ch ifch then GenToken assig Read ch elseGenToken colon GenToken stop Read ch enter GenToken line Read ch other LexicalError ch end end ProcedureIdentifier name string Beginname Append name ch Read ch whileisLetter ch orisDigit ch do Append name ch Read ch End Micro语言的词法分析程序的相关子程序 1 读标识符 保留字 关键字 Identifier name 从输入流把当前标识符名读到name中 它可能是保留字 在调用时 当前字符一定是字母 且已被读到ch中 isLetter ch 如果ch是字母 则取true 否则取false isDigit ch 如果ch是数字 则取true 否则取false ProcedureConstant class classType C ConsstType BeginIntConst N1 L1 ifch then Read ch if IsDigit ch LexicalError ch IntConst N2 L2 class realC C N1 N2 1 0 10 L2 Else class intC C N1 End Micro语言的词法分析程序的相关子程序 2 读整 实常数 Constant class C 从输入流读到当前常数 并在class中给出常数的类型标志 C中给出常数的二进制数值 调用时当前字符定是数字 在ch中 整数 小数点左部 整数 小数点右部 Micro语言的词法分析程序的相关子程序 3 读整常数 IntConst N L 从输入流读当前整常数 并在N中给出所读常数的二 十 进制值 在L中给出整常数的位数 调用时当前字符应是数字 ProcedureIntConst N L BeginN Num ch L 1 Read ch whileisDigit ch do N N 10 Num ch L L 1 Read ch End Num ch 表示数字字符ch对应的二 十 进制值 3 语法分析程序思路 声明检查 beginvarid real 声明的位置 赋值语句标识符单词输入语句表达式整 实常数语句检查 输出语句左括号后继符 语句末符号 enterend 2 Micro语言的语法分析1 任务 检查程序是否有语法 语法结构 上的错误2 输入 词法分析后得到的Token表输出 具体语法错误提示和语法全部正确提示 位置的正确性 4 Micro语言的语法分析程序 ProcedureParser beginMatch begin 1 Match var 2 LD Match id 3 Match colon 4 Match intC reaC 5 Match semi 6 ReadToken token iftoken linethenReadToken token iftoken varthengotoLD Match kind n 读当前Token 并检查Token LH kind 若不等 则打出错误编号n Token LH Token的左半部 Token RH Token的右半部 ReadToken token 把当前Token读到token中 声明 LS casetokenof write Match Lparen 7 Expr Match Rparen 8 read Match Lparen 9 Match id 10 Match Rparen 11 id Match assig 12 Expr other error 13 end ReadToken token 读语句的后继符 语句 单词 后继符 casetokenof semi ReadToken token iftoken linethenReadToken token gotoLS lineMatch end end ReadToken token iftoken stopthenSTOPelseError 14 other Error 15 endend Micro语言的语法分析子程序 表达式的语法检查 Error1程序头不是beginError2变量声明头不是varError3var后不是标识符Error4 varid 后不是 Error5 varid 后不是类型符Error6变量声明后不是 Error7write后不是 Error8 write E 后不是 Error9read后不是 Error10 read 后不是 id Micro语言的具体语法错误 Error11 read id 后不是 Error12赋值语句左部不是 Error13语句头单词错Error14程序结束符错Error15语句后继符错Error16缺 E 中的闭括号Error17运算分量的后继符错 2 4Micro语言的语义分析 1 任务 语法分析 只检查位置的正确性不检查他本身 语义 的正确性语义分析 主要是类型匹配问题将Token序列中的标识符转换为 id entry entry 变量的属性表 符号表 地址 X 表示变量名 或常数 X的符号表地址 Micro语言的语义分析程序 ProcedureSemantic beginCreat 建空符号表ReadToken 读 beginLD ReadToken token casetoken LHof var ReadToken token Enter token RH Entry s ifs truethenError 1 重复声明错ReadToken ReadToken token int realcasetoken LHof intSetAttribute entry newAddr intType realSetAttribute entry newAddr realType end ReadToken gotoLD Enter name Entry s 将name填入符号表 并在entry中给出其表项地址 若已有同名项 则s取true值 否则取false SetAttribute entry Addr Type 将标识符的地址和类型填入符号表的entry项内 otherwhiletoken stopdo iftoken LH idthenFind token RH entry s ifs falsethenError 2 无声明错ChangeToken entry end Find name entry s 用name查找符号表 并在addr和type中给出其name的地址和类型 若已有同名项 则s取true值 否则取false ChangeToken entry 将被读token 标识符 的右半部改为entry地址 2 5Micro语言的目标代码 1 采用三地址形式的目标语言 其指令如下 addd1d2d3 d3 d1 d2 muld1d2d3 d3 d1 d2 stod1d2 d2 d1 inpd1输入d1outd1输出d1 例 表达式a b c d的目标代码 2 Micro语言的目标代码生成程序 ProcedureGenCodeS beginLS ReadNewToken tk caseLH tk of id Search RH tk vAddr vType ReadNewToken GenCodeE eAddr SemanStack top addr eType SemanStack top Type if Equ vType eType thenError 1 Sendcode STO eAddr vAddr POP Search RH tk vAddr vType 用符号表的某项地址entry求变量的地址和类型 SemanStack top 表示SemanStack的顶元素Sendcode code 把代码code送入代码区 赋值的左边 赋值的右边 类型不相容错 write ReadNewToken 读 GenCodeE eAddr SemanStack top addr Sendcode OUT eAddr POP ReadNewToken 读 read ReadNewToken tk Search RH tk vAddr vType 求变量地址Sendcode INP vAddr end ReadNewToken tk iftk semithengotoLSelseSendCode STOP end 无括号表达式的目标代码生成程序 ProcedureGenCodeE beginL0 ReadNewToken tk L1 casetkof id entry Search entry vAddr vType 求变量地址push vAddr vType gotoL0 intC val push val int gotoL0 reaC val push val real gotoL0 plus multiftop 1gotoL1 end 判断优先级 ProduceCode 用语义栈SemanStack的内容生成代码 ProcedureProduceCode beginif Equa typ1 typ2 thenError else temp NewAddr SendCode OP Addr1 Addr1 temp Pop 3 push temp typ1 end ProduceCode 用语义栈SemanStack的内容生成代码 带括号表达式的目标代码生成程序 ProcedureGenCodeE beginpushOperator L0 ReadNewToken tk L1 casetkof id entry Search entry vAddr vType pushOperand vAddr vType gotoL0 intC val pushOperand val int gotoL0 reaC val pushOperand val real gotoL0 Lparen pushOperator gotoL0 OperandStack 分量栈OperatorStack 运算符栈 带括号表达式的目标代码生成程序 接上 plus multcaseOperatorStack top of pushOperator tok gotoL0 plus mult