SPIR-V 研究：编译器基本原理（三） - Chomsky文法分类

标签（空格分隔）： SPIR-V Vulkan Grammar

上一篇说过语法分为四类；这一篇来介绍Chomsky Hierarchy。首先，我们简单看看type-0和type-1的语法。

Type-0 - Unrestricted grammar

这是一种没有任何限制的语法，理论上可以描述任何图林机可以接受的语言。它的一般形式如下图：

这是一个从u生成v的过程；其中u，v是任意字符组合（包括最终字符和中间符号，或空字符），当然u至少包含一个中间符号。数学表达式为：(Σ ? N)* N (Σ ? N)* --> (Σ ? N)*
虽然，type-0很强大，但是用它来检验语句是否符合语法规则，也就是写一个一般性通用的Parser，是非常困难的事。这也就引出了后面几种语法；其想法是通过加强限制条件，我们可以得到更简单更容易使用的语法。

Type-1- Context-sensitive grammar (CSG)

这是一种上下文有关的语法规则；左侧和右侧被替换的字符前后都有可能有别的字符，也就是有上下文的；只