Meh*_*dad 59 c++ grammar d context-free-grammar
我几个月前在D新闻组上发布了这个,但由于某种原因,答案从未真正说服过我,所以我想我会在这里问.
但是,C++的语法不是(即使没有宏).(请仔细阅读!)
现在被授予,我对编译器,词法分析器和解析器一无所知(正式).我所知道的只是我在网上学到的东西.
以下是(我相信)我对上下文的理解,在非技术术语中:
语言的语法是无上下文的,当且仅当你能够总是理解给定代码片段的含义(尽管不一定是确切的行为)而不需要在任何其他地方"看".
或者,更严格:
如果我需要,语法不能无上下文我只是通过查看它就无法告诉表达式的类型.
因此,例如,C++失败上下文测试,因为意义的confusing<sizeof(x)>::q < 3 > (2) 依赖于值的q.
到现在为止还挺好.
现在我的问题是:可以对D说同样的话吗？
例如,在D中,可以通过Value[Key]声明创建哈希表
int[string] peoplesAges; // Maps names to ages
静态数组可以用类似的语法定义:
int[3] ages; // Array of 3 elements
模板可以用来使它们混淆:
template Test1(T...)
{
alias int[T[0]] Test;
}
template Test2(U...)
{
alias int[U] Test2; // LGTM
}
Test1!(5) foo;
Test1!(int) bar;
Test2!(int) baz; // Guess what? It's invalid code.
这意味着我无法分辨它的意思T[0]或U只是通过观察它(即它可能是一个数字,它可能是一种数据类型,或者它可能是一个神知道什么的元组).我甚至无法判断表达式是否在语法上有效(因为int[U]当然不是 - 你不能将元组作为键或值的哈希表).
我试图制作的任何解析树Test都没有任何意义(因为它需要知道节点是否包含数据类型而不是文字或标识符),除非它将结果延迟到T已知值(使其成为已知)依赖于上下文的).
我只是想我会发表评论:看到答案非常有趣,因为:
我不知道我是在学习还是变得更加困惑,但无论哪种方式,我都很高兴我问过这个问题...感谢您花时间回答,大家好!
APr*_*mer 42
无上下文首先是生成语法的属性.这意味着非终端可以生成的内容将不依赖于非终端出现的上下文(在非上下文无关的生成语法中,"由给定的非终端生成的字符串"的概念通常很难界定).这并不妨碍两个非终端生成相同的符号串(因此相同的符号串出现在具有不同含义的两个不同的上下文中)并且与类型检查无关.
如果至少有一个描述它的上下文无关语法,则通过声明语言是无上下文的,将无上下文定义从语法扩展到语言是很常见的.
在实践中,没有编程语言是无上下文的,因为诸如"变量必须在使用之前声明"之类的东西不能通过无上下文语法来检查(它们可以被其他类型的语法检查).这还不错,实际上要检查的规则分为两部分:你要用语法检查的那些和你在语义传递中检查的规则(这种划分也允许更好的错误报告和恢复,所以你有时候想要接受更多的语法,而不是为了给用户提供更好的诊断能力.
人们通过声明C++不是无上下文的意思是,以一种方便的方式进行这种划分是不可能的(方便地包括作为标准"遵循几乎官方语言描述"和"我的解析器生成器工具支持那种划分";允许语法含糊不清,语义检查要解决的歧义是一种相对简单的方法来完成C++的切割,并遵循C++标准,但是当你依赖于工具时这很不方便不允许含糊不清的语法,当你有这样的工具时,很方便).
我不太了解D,在语义检查的无上下文语法中是否有方便的语言规则切割,但你所展示的并不是证明没有的情况.
Nic*_*tti 21
无上下文的属性是一个非常正式的概念; 你可以在这里找到一个定义.请注意,它适用于语法:如果存在至少一个识别它的上下文无关语法,则称该语言是无上下文的.请注意,可能存在识别相同语言的其他语法,可能不是上下文.
基本上它意味着语言元素的定义不能根据它周围的元素而改变.语言元素我指的是表达式和标识符等概念,而不是程序内部这些概念的特定实例,如a + b或count.
让我们试着建立一个具体的例子.考虑一下这个简单的COBOL语句:
01 my-field PICTURE 9.9 VALUE 9.9.
这里我定义了一个字段,即一个变量,其大小设置为保存一个整数位,小数点和一个十进制数字,初始值为9.9.一个非常不完整的语法可能是:
field-declaration ::= level-number identifier 'PICTURE' expression 'VALUE' expression '.'
expression ::= digit+ ( '.' digit+ )
不幸的是,可以遵循的有效表达式与可以遵循PICTURE的有效表达式不同VALUE.我可以用我的语法重写第二个作品如下:
'PICTURE' expression ::= digit+ ( '.' digit+ ) | 'A'+ | 'X'+
'VALUE' expression ::= digit+ ( '.' digit+ )
这将使我的语法上下文敏感,因为expression根据它是在之后'PICTURE'还是之后被发现而将是不同的'VALUE'.但是,正如已经指出的那样,这并没有说明底层语言.一个更好的选择是:
field-declaration ::= level-number identifier 'PICTURE' format 'VALUE' expression '.'
format ::= digit+ ( '.' digit+ ) | 'A'+ | 'X'+
expression ::= digit+ ( '.' digit+ )
这是无背景的.
如您所见,这与您的理解截然不同.考虑:
a = b + c;
在没有查找a,b和c的声明的情况下,你可以对这个声明说几乎没有,这是有效声明的任何语言,但这本身并不意味着任何这些语言都不是没有上下文.可能令你感到困惑的是,背景自由与模糊性不同.这是C++示例的简化版本:
a < b > (c)
这是不明确的,因为单独查看它无法判断这是函数模板调用还是布尔表达式.另一方面,前面的例子并不含糊不清; 从语法的角度来看,它只能被解释为:
identifier assignment identifier binary-operator identifier semi-colon
在某些情况下,您可以通过在语法级别引入上下文敏感度来解决歧义.我不认为上面这个含糊不清的例子就是这种情况:在这种情况下,你不能在不知道a是否是模板的情况下消除歧义.请注意,当此类信息不可用时,例如,当它取决于特定的模板专业化时,该语言提供了解决歧义的方法:这就是您有时必须使用typename模板中的某些类型或template在调用成员时使用的原因功能模板.
已经有很多好的答案,但由于你不了解语法,解析器和编译器等,让我通过一个例子来证明这一点.
首先,语法的概念非常直观.想象一套规则:
S -> a T
T -> b G t
T -> Y d
b G -> a Y b
Y -> c
Y -> lambda (nothing)
并想象一下你S.大写字母是非终端的,小写字母是终端.这意味着如果你得到所有终端的句子,你可以说语法生成该句子作为语言中的"单词".想象一下用上面的语法进行这样的替换(*phrase*之间的短语是被替换的那个):
*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
但更复杂的是,确保variablein声明与正在计算的声明匹配.
无论如何,我只想给你一个想法.所以,所有这些都是上下文相关的:
member存在obj于代码中:obj.member;或}我希望你知道有什么不同(如果你没有,我会非常乐意解释).
总结如下:
但不一定总是这样.这只是向您展示了每个级别如何变得更强大以便能够执行更多操作.但是,每个提到的编译器级别实际上可能更强大.
例如,我不记得的一种语言,使用数组订阅和函数调用括号,因此它需要解析器查找变量的类型(上下文相关的东西)并确定哪个规则(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必须在某个时刻检查某些内容在其他地方的定义,只是说该程序在结构上是正确的,那么它的语法就不是无上下文的.如果你隔离代码的任何部分,它仍然可以说它在结构上是正确的,那么它是无上下文的.
如果我需要,语法不能无上下文我只是通过查看它就无法告诉表达式的类型.
不,那是错的.如果你只是通过查看它和解析器的当前状态(我在函数中,在命名空间中等)来判断它是否是表达式,那么语法就不能没有上下文了.
然而,表达式的类型是语义,而不是语法,解析器和语法不会给出类型或语义有效性的一分钱,或者你是否可以将元组作为哈希映射中的值或键,或者如果你在使用它之前定义了该标识符.
语法不关心它意味着什么,或者是否有意义.它只关心它是什么.
D'lexer中有一个结构:
string ::= q" Delim1 Chars newline Delim2 "
其中Delim1和Delim2是匹配的标识符,而Chars不包含换行符Delim2.
这个构造是上下文敏感的,因此D的词法分析器语法是上下文敏感的.
自从我使用D语法以来已经有好几年了,所以我不记得我脑子里的所有麻烦点,或者即使其中任何一个让D的解析器语法上下文敏感,但我相信他们这样做了不.从回忆中,我会说D的语法是无上下文的,而不是任何k的LL(k),并且它具有令人讨厌的模糊性.
要回答编程语言是否无上下文的问题,您必须首先确定在语法和语义之间划分界限的位置.作为一个极端的例子,在C中,一个程序在被允许溢出后使用某些整数的值是非法的.很明显,这在编译时无法检查,更不用说解析时间了:
void Fn() {
int i = INT_MAX;
FnThatMightNotReturn(); // halting problem?
i++;
if(Test(i)) printf("Weeee!\n");
}
作为其他人指出的一个不太极端的例子,使用规则之前的减速不能在无上下文语法中强制执行,因此如果您希望保持语法传递上下文无关,那么必须将其推迟到下一次传递.
作为一个实际的定义,我将从以下问题开始:你能否正确无误地使用无上下文语法确定所有正确程序的解析树,并且对于所有不正确的程序(语言需要被拒绝),要么拒绝它们语法无效或产生一个解析树,后来的传递可以识别为无效并拒绝？
鉴于D语法的最正确的规范是解析器(IIRC是LL解析器),我强烈怀疑它实际上是由我建议的定义上下文.
注意:上面没有说明语言文档或给定解析器使用的语法,只有在存在无上下文语法的情况下.此外,关于D语言的唯一完整文档是编译器DMD的源代码.
| 归档时间： |
|
| 查看次数： |
5801 次 |
| 最近记录： |