在上下文无关文法的基础上,为每个文法符号(终结符或非终结符)配备若干相关的“值”(称为属性),这些属性代表与文法符号相关信息,例如它的类型、值、代码序列、符号表内容等等。
属性与变量一样,可以进行计算和传递。
属性加工的过程既是语义处理的过程。
对于文法的每个产生式都配备了一组属性的计算规则,称为语义规则。
A=(G,V,F) G:是一个上下文无关文法 V:有穷的属性集,每个属性与文法的一终结符或非终结符相连 F:关于属性的属性断言或谓词集。每个断言与一个产生式相联。一个断言就是一个语义规则,描述各属性之间的关系。
为每个符号设置一个属性,终结符号用单词属性。 为每个产生式设置语义规则--描述各属性的关系。
属性文法的思想:首先对于每个文法符号引进相关的属性符号,其次对于每个产生式写出属性值计算的规则。
综合属性:在语法树中,一个结点的综合属性由该结点的子结点的属性值确定,它的计算规则由底向上。
继承属性:在语法树中,一个结点的基础属性有盖结点的父结点或兄弟结点的属性确定,即它的计算规则由顶向下。
中间代码的形式:逆波兰式、四元式、三元式、间接三元式、树
2.1 逆波兰式(后缀表达式)
逆波兰式是最简单的一种中间代码表示形式,将运算对象写在前面,把运算符号写在后面。
最大的优点是易于计算机处理表达式。
例如 a+b*(c+d/e) 的逆波兰式为 abcd/+*+
2.2 三元式和树
三元式有三个部分组成:算符op,第一运算对面ARG1,第二运算对象ARG2
树形表示是三元式表示的翻版。
例如 a := bc+bd 的三元式为: (1)(,b,c) (2)(,b,d) (3)(+(1),(2)) (4)(:=(3),a)
2.3 四元式
四元式的四个组成成分是:算符op,第一和第二运算对象ARG1和ARG2,及运算结果RESULT。
把(jump,-,-,L)写成goto L 把(jrop,B,C,L)写成if B rop C goto L
例如 a := bc + bd 的四元式为 (1)(,b,c,t1) (2)(,b,d,t2) (3)(+,t1,t2,t3) (4)(:=,t3,-,a)
分析方法主要分为自顶向下的语法分析和自底向上的语法分析两类,自顶向下的语法分析主要对应于LL文法,而自底向上的语法分析主要对应于LR文法。 LALR分析器是一种规范LR分析方法的简化形式。它可以对上下无关文法进行语法分析。LALR即“Look-AheadLR”。其中,Look-Ahead为“向前看”,L代表对输入进行从左到右的检查,R代表反向构造出最右推导序列。 LALR分析器可以根据一种程序设计语言的正式语法的产生式而对一段文本程序输入进行语法分析,从而在语法层面上判断输入程序是否合法。 实际应用中的LALR分析器并不是由人手工写成的,而是由类似于yacc和GNU Bison之类的LALR语法分析器生成工具构成。由机器自动生成的代码相比较于程序员手工的代码,拥有更好的运行效率而且减少了程序员的工作量。
LR算法是Logistic Regression的简写,即逻辑回归算法。 LR分析器是一种由下而上(bottom-up)的上下文无关语法分析器。LR意指由左(Left)至右处理输入字符串,并以最右边优先派生(Right derivation)的推导顺序(相对于LL分析器)建构语法树。能以此方式分析的语法称为LR语法。而在LR(k)这样的名称中,k代表的是分析时所需前瞻符号(lookahead symbol)的数量,也就是除了目前处理到的输入符号之外,还得再向右引用几个符号之意;省略 (k)时即视为LR(1),而非LR(0)。