语法分析

上下文无关文法 语法分析器
· LL剖析器
· 算符优先分析器
· LR剖析器
· SLR剖析器
· LALR剖析器

在计算机科学和语言学中，语法分析（英語：syntactic analysis，也叫 parsing）是根据某种给定的形式文法对由单词序列（如英语单词序列）构成的输入文本进行分析并确定其语法结构的一种过程。

语法分析器（parser）通常是作为编译器或解释器的组件出现的，它的作用是进行语法检查、并构建由输入的单词组成的数据结构（一般是语法分析树、抽象语法树等层次化的数据结构）。语法分析器通常使用一个独立的词法分析器从输入字符流中分离出一个个的“单词”，并将单词流作为其输入。实际开发中，语法分析器可以手工编写，也可以使用工具（半）自动生成。

语法分析器分类

语法分析器的任务主要是确定是否可以以及如何从语法的起始符号推导出输入符号串（输入文本），主要可以通过两种方式完成：

• 自顶向下分析：根据形式语法规则，在语法分析树的自顶向下展开中搜索输入符号串可能的最左推导。单词按从左到右的顺序依次使用。
• 自底向上分析：语法分析器从现有的输入符号串开始，尝试将其根据给定的形式语法规则进行改写，最终改写为语法的起始符号。

参考文献

书籍

• Chapman, Nigel P., LR Parsing: Theory and Practice（页面存档备份，存于互联网档案馆）, Cambridge University Press, 1987. ISBN 0-521-30413-X.
• Grune, Dick; Jacobs, Ceriel J.H., Parsing Techniques - A Practical Guide（页面存档备份，存于互联网档案馆）, VU University Amsterdam, Amsterdam, The Netherlands. Originally published by Ellis Horwood, Chichester, England, 1990; ISBN 0-13-651431-6.

外部連結

• Objective-C parser written in C#
• The Lemon LALR Parser Generator

参见

• 词法分析