已经有很多好的回答了,但是由于您对语法、解析器和编译器等方面不太了解,让我通过一个例子来演示一下。
首先,语法的概念相当直观。想象一组规则:
S -> a T
T -> b G t
T -> Y d
b G -> a Y b
Y -> c
Y -> lambda (nothing)
假设你从S
开始。大写字母代表非终结符,小写字母代表终结符。这意味着如果你得到一个由所有终结符组成的句子,你可以说语法生成了该句子作为语言中的“单词”。想象一下使用上述语法进行这样的替换(*短语*之间的短语是被替换的短语):
*S* -> a *T* -> a *b G* t -> a a *Y* b t -> a a b t
那么,我可以用这个语法来创建 aabt
。
好的,回到主线。
让我们假设有一种简单的语言。您有数字、两种类型(int和string)和变量。您可以在整数上进行乘法,在字符串上进行加法,但不能反过来进行操作。
首先需要的是一个词法分析器。通常这是一个正则文法(或等同于它的DFA,或者等同于正则表达式),用于匹配程序中的令牌。通常使用正则表达式来表示它们。在我们的示例中:
(我随意编写了这些语法)
number: [1-9][0-9]* // One digit from 1 to 9, followed by any number
// of digits from 0-9
variable: [a-zA-Z_][a-zA-Z_0-9]* // You get the idea. First a-z or A-Z or _
// then as many a-z or A-Z or _ or 0-9
// this is similar to C
int: 'i' 'n' 't'
string: 's' 't' 'r' 'i' 'n' 'g'
equal: '='
plus: '+'
multiply: '*'
whitespace: (' ' or '\n' or '\t' or '\r')* // to ignore this type of token
现在,您已经拥有了一个常规的语法,可以对输入进行分词,但它并不理解其结构。
然后您需要一个解析器。解析器通常是上下文无关文法。上下文无关文法意味着,在文法中,您只有单个非终结符出现在文法规则的左侧。在本答案开头的示例中,规则如下:
b G -> a Y b
这使得语法上下文变得敏感,因为左侧有b G
而不仅仅是G
。这是什么意思呢?
当你编写语法时,每个非终结符都有一个含义。让我们为我们的示例编写一个上下文无关文法(|表示或。就像在同一行中编写多个规则):
program -> statement program | lambda
statement -> declaration | executable
declaration -> int variable | string variable
executable -> variable equal expression
expression -> integer_type | string_type
integer_type -> variable multiply variable |
variable multiply number |
number multiply variable |
number multiply number
string_type -> variable plus variable
现在这个语法可以接受这段代码:
x = 1*y
int x
string y
z = x+y
从语法上讲,这段代码是正确的。那么,让我们回到什么是无上下文语法的意思。正如你在上面的例子中看到的,当你展开executable
时,你会生成一个形式为variable = operand operator operand
的语句,而不考虑你所在代码的哪个部分。无论是开始还是中间,无论变量是否被定义,或者类型是否匹配,你都不知道也不关心。
接下来,你需要语义。这就是上下文敏感语法发挥作用的地方。首先,让我告诉你,在现实中,没有人真正编写上下文敏感语法(因为解析它太困难了),而是编写解析输入时解析器调用的一些代码片段(称为动作例程,虽然这不是唯一的方法)。然而,从形式上讲,你可以定义所有你需要的。例如,为了确保在使用变量之前定义它,而不是这样
executable -> variable equal expression
你需要有类似于以下的东西:
你必须拥有类似于以下的东西:
declaration some_code executable -> declaration some_code variable equal expression
虽然更加复杂,但要确保声明中的变量
与正在计算的变量匹配。
总之,我只是想给你一个想法。所以,所有这些都是上下文敏感的:
- 类型检查
- 函数参数的数量
- 函数的默认值
- 如果代码中
obj.member
中存在member
在obj
中
- 几乎所有不像:缺少
;
或}
我希望你知道它们之间的区别(如果你不知道,我很愿意解释)。
所以总结一下:
- 词法分析器使用正则语法对输入进行标记化
- 解析器使用上下文无关文法来确保程序处于正确的结构中
- 语义分析器使用上下文相关文法进行类型检查、参数匹配等等
然而,并不总是这样。这只是向你展示了每个级别需要变得更强大才能做更多事情。然而,上述每个编译器级别实际上都可以更强大。
例如,我不记得的一种语言,使用括号进行数组订阅和函数调用,因此需要解析器查找变量的类型(上下文相关的相关内容)并确定要采取哪个规则(function_call或array_substitution)。
如果您设计一个具有重叠的正则表达式的词法分析器,则还需要查找上下文以确定正在匹配哪种类型的标记。
回答您的问题!通过您提到的示例,很明显c++语法不是上下文无关的。至于D语言,我完全不知道,但现在你应该能够理性思考了。这样想:在上下文无关文法中,非终结符可以扩展而不考虑任何东西,但只考虑语言的结构。就像你说的那样,它会扩展,而不“看”其他地方。
一个熟悉的例子是自然语言。例如,在英语中,你会说:
sentence -> subject verb object clause
clause -> .... | lambda
好的,这里的非终结符是sentence
和clause
。使用这个语法,你可以创建这些句子:
I go there because I want to
或者
I jump you that I is air
如您所见,第二个句子有正确的结构,但是没有意义。就上下文无关语法而言,意义并不重要。它只是将
verb
扩展为任何动词,而不“查看”其余部分的句子。
因此,如果您认为D必须在某个时候检查其他地方的定义方式,仅仅为了说程序在结构上是正确的,那么它的语法就不是上下文无关的。如果您隔离代码的任何部分,它仍然可以说它在结构上是正确的,那么它就是上下文无关的。
a * b
是什么意思? - Bo Persson