D의 문법은 정말 문맥이없는가요?

D의 문법은 정말 문맥이없는가요?

---

몇 달 전에 D 뉴스 그룹에이 글을 올렸지 만 어떤 이유에서인지 답이 저를 설득하지 못했기 때문에 여기에서 물어볼 것이라고 생각했습니다.

---

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그것을 만드는 (알려져있다 상황에 따라 다름).

이 점을 감안할 때 D는 실제로 컨텍스트가 없습니까? 아니면 개념을 오해하고 있습니까?

왜 왜 안돼?

---

최신 정보:

다음과 같은 이유로 답변을 보는 것은 정말 흥미 롭습니다.

• 일부 답변은 C ++ 및 D 가 컨텍스트 프리가 될 수 없다고 주장합니다.
• 일부 답변은 C ++와 D가 모두 컨텍스트 가 없다고 주장합니다.
• 일부 답변은 C ++가 상황에 맞는 반면 D는 그렇지 않다는 주장을 뒷받침합니다.
• 아무도 C ++가 문맥에 자유롭고 D는 문맥에 민감하다고 주장하지 않았습니다. :-)

내가 배우고 있는지, 더 혼란스러워 지는지는 모르겠지만, 어느 쪽이든 물어봐서 기쁩니다 ... 시간을내어 답 해주셔서 감사합니다, 여러분!

---

문맥에서 자유 롭다는 것은 먼저 생성 문법의 속성입니다. 이는 비 터미널이 생성 할 수있는 것이 비 터미널이 나타나는 문맥에 의존하지 않는다는 것을 의미합니다 (비 맥락없는 생성 문법에서 "주어진 비 터미널에 의해 생성 된 문자열"이라는 개념은 일반적으로 어렵습니다. 정의). 이것은 두 개의 비 터미널에 의해 동일한 기호 문자열이 생성되는 것을 방지하지 않으며 (따라서 동일한 기호 문자열이 다른 의미를 가진 두 개의 다른 컨텍스트에 표시되도록) 유형 검사와 관련이 없습니다.

문맥이없는 정의를 문법에서 언어로 확장하는 것은 일반적으로 언어를 설명하는 문맥 자유 문법이 하나 이상있는 경우 문맥 자유 롭다고 말함으로써 언어로 확장됩니다.

실제로 "변수를 사용하기 전에 선언해야합니다"와 같은 것은 문맥 자유 문법 (다른 종류의 문법으로 확인할 수 있음)으로 확인할 수 없기 때문에 어떤 프로그래밍 언어도 문맥 자유롭지 않습니다. 이것은 나쁘지 않습니다. 실제로 확인할 규칙은 문법으로 확인하려는 규칙과 의미 론적 패스에서 확인하는 규칙으로 나뉩니다 (그리고이 분할은 또한 더 나은 오류보고 및 복구를 허용하므로 때때로 사용자에게 더 나은 진단을 제공하기 위해 가능한 것보다 더 많은 문법을 받아들이기를 원합니다.)

C ++은 문맥 자유 아니라고 진술에 의해 어떤 사람들 수단이 부문을 수행하기로 (편리한 방법으로 가능하지 않다는 것이다 편리 기준으로 포함하고 종류가 "내 파서 생성기 도구 지원"거의 공식 언어 설명을 다음 " 문법을 모호하게하고 의미 검사를 통해 모호함을 해결하도록 허용하는 것은 C ++에 대한 컷을 수행하고 C ++ 표준을 따르는 비교적 쉬운 방법이지만, 다음과 같은 도구에 의존 할 때는 불편합니다. 모호한 문법을 ​​허용하지 마십시오. 그러한 도구가 있으면 편리합니다.)

나는 D에 대해 충분히 알지 못합니다. 의미 검사가있는 문맥없는 문법에서 언어 규칙의 편리한 부분이 있는지 여부를 알 수는 없지만, 당신이 보여주는 것은 사례가 없다는 것을 증명하는 것과는 거리가 멀습니다.

---

문맥이 자유 롭다는 속성은 매우 형식적인 개념입니다. 여기 에서 정의를 찾을 수 있습니다 . 이는 문법에 적용된다는 점에 유의하십시오 . 언어를 인식하는 문맥 자유 문법이 하나 이상 있으면 문맥 자유 언어라고합니다. 동일한 언어를 인식하는 다른 문법 (문맥 자유가 아닐 수 있음)이있을 수 있습니다.

기본적으로 의미하는 것은 언어 요소의 정의가 주변 요소에 따라 변경 될 수 없다는 것입니다. 언어 요소 란 또는 같은 프로그램 내에서 이러한 개념의 특정 인스턴스가 아니라 표현식 및 식별자 와 같은 개념을 의미 합니다.a + bcount

구체적인 예를 들어 보겠습니다. 다음과 같은 간단한 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코드의 어느 부분에 있는지 고려하지 않고 양식의 하나의 문을 생성 합니다. 맨 처음이든 중간이든, 변수가 정의되었는지 여부 또는 유형이 일치하는지 여부는 알 수 없으며 상관하지 않습니다.

Next, you need semantics. This is were context-sensitive grammars come into play. First, let me tell you that in reality, no one actually writes a context sensitive grammar (because parsing it is too difficult), but rather bit pieces of code that the parser calls when parsing the input (called action routines. Although this is not the only way). Formally, however, you can define all you need. For example, to make sure you define a variable before using it, instead of this

executable -> variable equal expression

you have to have something like:

declaration some_code executable -> declaration some_code variable equal expression

more complex though, to make sure the variable in declaration matches the one being calculated.

Anyway, I just wanted to give you the idea. So, all these things are context-sensitive:

• Type checking
• Number of arguments to function
• default value to function
• if member exists in obj in code: obj.member
• Almost anything that's not like: missing ; or }

I hope you got an idea what are the differences (If you didn't, I'd be more than happy to explain).

So in summary:

• Lexer uses a regular grammar to tokenize input
• Parser uses a context-free grammar to make sure the program is in correct structure
• Semantic analyzer uses a context-sensitive grammar to do type-checking, parameter matching etc etc

It is not necessarily always like that though. This just shows you how each level needs to get more powerful to be able to do more stuff. However, each of the mentioned compiler levels could in fact be more powerful.

For example, one language that I don't remember, used array subscription and function call both with parentheses and therefore it required the parser to go look up the type (context-sensitive related stuff) of the variable and determine which rule (function_call or array_substitution) to take.

If you design a language with lexer that has regular expressions that overlap, then you would need to also look up the context to determine which type of token you are matching.

To get to your question! With the example you mentioned, it is clear that the c++ grammar is not context-free. The language D, I have absolutely no idea, but you should be able to reason about it now. Think of it this way: In a context free grammar, a nonterminal can expand without taking into consideration anything, BUT the structure of the language. Similar to what you said, it expands, without "looking" anywhere else.

A familiar example would be natural languages. For example in English, you say:

sentence -> subject verb object clause
clause -> .... | lambda

Well, sentence and clause are nonterminals here. With this grammar you can create these sentences:

I go there because I want to

or

I jump you that I is air

As you can see, the second one has the correct structure, but is meaningless. As long as a context free grammar is concerned, the meaning doesn't matter. It just expands verb to whatever verb without "looking" at the rest of the sentence.

So if you think D has to at some point check how something was defined elsewhere, just to say the program is structurally correct, then its grammar is not context-free. If you isolate any part of the code and it still can say that it is structurally correct, then it is context-free.

---

The grammar cannot be context-free if I need I can't tell the type of an expression just by looking at it.

No, that's flat out wrong. The grammar cannot be context-free if you can't tell if it is an expression just by looking at it and the parser's current state (am I in a function, in a namespace, etc).

The type of an expression, however, is a semantic meaning, not syntactic, and the parser and the grammar do not give a penny about types or semantic validity or whether or not you can have tuples as values or keys in hashmaps, or if you defined that identifier before using it.

The grammar doesn't care what it means, or if that makes sense. It only cares about what it is.

---

There is a construct in D's lexer:

string ::= q" Delim1 Chars newline Delim2 "

where Delim1 and Delim2 are matching identifiers, and Chars does not contain newline Delim2.

This construct is context sensitive, therefore D's lexer grammar is context sensitive.

It's been a few years since I've worked with D's grammar much, so I can't remember all the trouble spots off the top of my head, or even if any of them make D's parser grammar context sensitive, but I believe they do not. From recall, I would say D's grammar is context free, not LL(k) for any k, and it has an obnoxious amount of ambiguity.

---

To answer the question of if a programming language is context free you must first decide where to draw the line between syntax and semantics. As an extreme example, it is illegal in C for a program to use the value of some kinds of integers after they have been allowed to overflow. Clearly this can't be checked at compile time, let alone parse time:

void Fn() {
  int i = INT_MAX;
  FnThatMightNotReturn();  // halting problem?
  i++;
  if(Test(i)) printf("Weeee!\n");
}

As a less extreme example that others have pointed out, deceleration before use rules can't be enforced in a context free syntax so if you wish to keep your syntax pass context free, then that must be deferred to the next pass.

As a practical definition, I would start with the question of: Can you correctly and unambiguously determine the parse tree of all correct programs using a context free grammar and, for all incorrect programs (that the language requires be rejected), either reject them as syntactically invalid or produce a parse tree that the later passes can identify as invalid and reject?

Given that the most correct spec for the D syntax is a parser (IIRC an LL parser) I strongly suspect that it is in fact context free by the definition I suggested.

---

Note: the above says nothing about what grammar the language documentation or a given parser uses, only if a context free grammar exists. Also, the only full documentation on the D language is the source code of the compiler DMD.

---

These answers are making my head hurt.

First of all, the complications with low level languages and figuring out whether they are context-free or not, is that the language you write in is often processed in many steps.

In C++ (order may be off, but that shouldn't invalidate my point):

1. it has to process macros and other preprocessor stuffs
2. it has to interpret templates
3. it finally interprets your code.

Because the first step can change the context of the second step and the second step can change the context of the third step, the language YOU write in (including all of these steps) is context sensitive.

The reason people will try and defend a language (stating it is context-free) is, because the only exceptions that adds context are the traceable preprocessor statements and template calls. You only have to follow two restricted exceptions to the rules to pretend the language is context-free.

Most languages are context-sensitive overall, but most languages only have these minor exceptions to being context-free.

참고URL : https://stackoverflow.com/questions/6982585/is-ds-grammar-really-context-free