首页 > 代码库 > 文法分析相关笔记
文法分析相关笔记
描述语言语法结构的形式规则称为文法。文法是一个四元组,具体组成如图所示。
文法一共四类,若文法G=(Vn,Vt,P,S)的每个产生式α→β,均有α∈(Vn∪Vt)*,则称G为0型文法。在0型文法上加以扩展,则得到以下文法:
1型文法:G的任何产生式α→β(S→ε除外)均满足左部中文法符号的个数小于右部文法的符号的个数,又称为上下文有关文法,意味着对非终结符的替换考虑必须考虑上下文(eg:有生产式如:αAB→Βcb,假设该生产式符合1型文法的生产式,则非终结符A只有在左边为α右边为B的情况才能转化为C)。
2型文法:G的任何产生式如A→β,其中A∈Vn,β∈(Vn∪Vt)*,上下文无关文法;
3型文法:G的任何产生式如A→α或A→αB,其中A、B∈Vn,a∈Vt,正规式。
推导/归约
推导就是从文法的开始符号S出发,反复使用生产式(P),将生产式左部的非终结符替换成右部的文发符号序列,知道产生一个终结符的序列位置。如果说α→β∈p,γ、λ∈V*,则γαλ=>γβλ称为文法G的一个直接推导,并称γαλ可直接推导出γβλ,反之即是直接归约(推导的逆过程)。如果α0=>α1=>…=>αn,则α0=>αn。
句型/句子/语言
如果文法G的开始符号为S,即从S推导出的字符串为一个句型。若X是S的一个句型,且X∈Vt*,则X是文法G的一个句子。仅含终结符的句型是一个句子。从文法G的开始符号出发,能推导出的句子全体成为语言,记为L(G)。如果L(G1)==L(G2),则G1==G2.
文法分析相关笔记
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。