语法分析器(Parser)
词法分析器的局限性
有限自动机本质只是计算待处理字符串关于他的状态数的模,只有结果,没有过程计数,不适用于嵌套结构的处理,如(){}等等
语法分析器定义
接收从词法分析器(lexer)1传来的一系列token,生成程序的语法树(展开嵌套结构 )
上下文无关文法(Context-free Grammars)
适用原因:程序具有天然的递归结构
特点:不关心token的attribute,只关心token的类型
由以下四部分组成
- 终结符(Terminal Symbols) :这些是文法中不能再分解的最基本的符号。在编程语言中,终结符可能包括关键字、操作符、标识符、常量等。在编译原理中,tokens即是终结符
- 非终结符(Nonterminals) 或 句法变量(Syntactic Variables) :这些符号代表文法中可以被进一步替换或展开的符号。它们通常用来表示语法结构中的抽象概念,如句子、表达式等。
- 产生式(Productions) :产生式是文法中定义如何从非终结符生成终结符序列或非终结符序列的规则。每个产生式由一个非终结符(头部或左侧)和一个字符串(体部或右侧)组成,字符串可以包含终结符和非终结符。
- 开始符号(Start Symbol) :这是文法中的一个特殊非终结符,整个文法生成过程从这个符号开始。开始符号用于生成语言中的所有可能字符串。
由开始符号开始,通过产生式一路推导所有的表达式,检测源代码是否可能出现
上下文重写器(CFG)
上下文无关文法仅仅只能给出是或否的答案,只能判断源代码的语法是否正确,我们需要CFG来生成语法分析树
推导(derivation)
最左推导
特征
- 叶节点均为终结符
- 根节点为非终结符
最右推导
最左推导和最右推导结果等同,仅仅是推导顺序的差别
歧义(ambiguity)
推导可以产生多种语法树,造成语法二义性
解决方法: 强行规定语法顺序
- 更改推导式,消除二义性
- 不规定语法顺序,通过先例声明和关联声明消除二义性(%left代表左结合,后声明的具有更高结合优先级)(图中所使用的是Bison的语法标记)
词法分析器(lexer)
词法分析器 = 正则表达式 + DFA/NFA
有限状态机
接受输入a,由状态s1转到s2,继续接收内容,直到reject状态
发生状态转换,但是输入指针不变
确定性有限自动机(DFA)
- 单一输入有确定状态转换
- 不存在空状态转换
非确定性有限自动机(NFA)
- 单一输入多种转换
- 存在空状态转换
epsilon闭包。
指所有只通过空状态转换能抵达的状态机的集合,仅限于NFA
词法分析器实现流程
- 预处理,展开宏,去除排版字符
- 使用正则表达式实现关键词等等的匹配
- 根据语言特点绘制出NFA逻辑图,从头到尾读取
- 将NFA转换为DFA(可选)
- 根据DFA写状态转换表(二位数组或一维数组+指针(复用子数组压缩空间))
- 根据状态转换表循环读取预处理后的源代码,转换为token交给下一层parser ↩