C ++을 LR (1) 파서로 파싱 할 수없는 이유는 무엇입니까?

C ++을 LR (1) 파서로 파싱 할 수없는 이유는 무엇입니까?

---

파서 및 파서 생성기에 대해 읽고 있었고 wikipedia의 LR 파싱 페이지 에서이 문장을 발견했습니다.

LR 파서의 변형을 사용하여 많은 프로그래밍 언어를 파싱 할 수 있습니다. 주목할만한 예외 중 하나는 C ++입니다.

왜 그래야만하지? C ++의 어떤 특정 속성으로 인해 LR 파서로 구문 분석 할 수 없습니까?

Google을 사용하면 C가 LR (1)로 완벽하게 구문 분석 될 수 있지만 C ++에는 LR (∞)이 필요하다는 것을 알았습니다.

---

Lambda the Ultimate 에는 C ++에 대한 LALR 문법을 설명 하는 흥미로운 스레드가 있습니다 .

여기에는 C ++ 파싱에 대한 토론이 포함 된 PhD 논문 링크 가 포함되어 있습니다.

"C ++ 문법은 모호하고 상황에 따라 다르며 일부 모호성을 해결하기 위해 무한한 예측이 필요할 수 있습니다."

계속해서 많은 예제를 제공합니다 (pdf의 147 페이지 참조).

예는 다음과 같습니다.

int(x), y, *const z;

의미

int x;
int y;
int *const z;

다음과 비교하십시오 :

int(x), y, new int;

의미

(int(x)), (y), (new int));

(쉼표로 구분 된 표현식).

두 토큰 시퀀스는 초기 하위 시퀀스는 동일하지만 마지막 구문에 따라 다른 구문 분석 트리를 갖습니다. 명확하게하기 전에 임의로 많은 토큰이있을 수 있습니다.

---

LR 파서는 모호한 문법 규칙을 의도적으로 처리 할 수 ​​없습니다. (아이디어가 진행되고 있던 1970 년대에 이론을 더 쉽게 만들었습니다.)

C와 C ++ 모두 다음 문장을 허용합니다.

x * y ;

두 가지 다른 구문 분석이 있습니다.

1. x를 가리키는 포인터로 y를 선언 할 수 있습니다.
2. x와 y를 곱하여 답을 버릴 수 있습니다.

이제 후자가 어리 석고 무시해야한다고 생각할 수도 있습니다. 대부분은 당신에게 동의 할 것입니다. 그러나 부작용이있을 수있는 경우가 있습니다 (예 : 곱하기에 과부하가 걸리는 경우). 그러나 그것은 요점이 아닙니다. 포인트가 있는 두 개의 서로 다른 파싱이 때문에 프로그램이이 방법에 따라 다른 것을 의미 할 수 있어야 구문 분석되고있다.

컴파일러는 적절한 환경에서 적절한 정보를 수용해야하며, 다른 정보가없는 경우 (예 : x 유형에 대한 지식) 나중에 수행 할 작업을 결정하기 위해 둘 다 수집해야합니다. 따라서 문법은 이것을 허용해야합니다. 그리고 그것은 문법을 모호하게 만듭니다.

따라서 순수한 LR 구문 분석은이를 처리 할 수 ​​없습니다. Antlr, JavaCC, YACC 또는 전통적인 Bison과 같은 널리 사용되는 다른 파서 생성기 나 "순수한"방식으로 사용되는 PEG 스타일 파서도 사용할 수 없습니다.

더 복잡한 경우가 많이 있습니다 (템플릿 구문 분석에는 임의의 미리보기가 필요하지만 LALR (k)는 대부분의 k 토큰을 미리 볼 수 있음). 순수한 LR (또는 다른) 구문 분석을 처리하는 데에는 반례가 하나만 필요 합니다.

대부분의 실제 C / C ++ 파서는 추가 해킹과 함께 일종의 결정 론적 파서를 사용 하여이 예제를 처리합니다. 심볼 테이블 컬렉션과 파싱을 얽어 묶습니다 ... "x"가 발생하면 파서는 x가 유형인지 알 수 있습니다. 또는 두 개의 잠재적 구문 분석 중에서 선택할 수 있습니다. 그러나이 작업을 수행하는 파서는 컨텍스트가 없으며 LR 파서 (순수한 것 등)에는 컨텍스트가 없습니다.

이러한 명확성을 위해 LR 파서에서 규칙 당 축소 시간 의미 검사를 속이고 추가 할 수 있습니다. (이 코드는 종종 단순하지 않습니다). 대부분의 다른 파서 유형에는 구문 분석의 다양한 지점에서 의미 검사를 추가 할 수있는 수단이 있습니다.

충분히 속임수를 쓰면 LR 파서를 C와 C ++에서 사용할 수 있습니다. GCC 직원은 잠시 동안 수행했지만 수동 코딩 파싱을 포기했습니다. 더 나은 오류 진단을 원했기 때문입니다.

그러나 또 다른 접근 방법이 있습니다.이 방법은 훌륭하고 깨끗하며 기호 테이블 해커가없는 C 및 C ++을 잘 구문 분석합니다 .GLR parsers . 이들은 컨텍스트가없는 완전한 파서입니다 (효과적으로 무한한 예측을 가짐). GLR 파서는 단순히 두 구문 분석을 모두 받아 들여 모호한 구문 분석을 나타내는 "트리"(실제로 나무와 같은 방향이 지정된 비순환 그래프)를 생성합니다. 구문 분석 후 패스로 모호성을 해결할 수 있습니다.

우리는이 기술을 DMS 소프트웨어 리엔지니어링 Tookit의 C 및 C ++ 프론트 엔드에서 사용합니다 (2017 년 6 월 현재 MS 및 GNU 방언에서 전체 C ++ 17을 처리합니다). 수백만 줄의 대형 C 및 C ++ 시스템을 처리하는 데 사용되었으며, 소스 코드에 대한 완전한 세부 사항으로 AST를 생성하는 완전하고 정밀한 구문 분석 기능이 있습니다. ( C ++에서 가장 까다로운 구문 분석에 대해서는 AST를 참조하십시오 . )

---

문제는 이런 식으로 정의되지 않지만 흥미 롭습니다.

이 새로운 문법이 "문맥이없는"yacc 파서에 의해 완벽하게 파싱 될 수 있도록 필요한 C ++ 문법에 대한 가장 작은 수정 세트는 무엇입니까? (하나의 '해킹'만 사용하십시오 : typename / identifier disambiguation, 파서가 모든 typedef / class / struct를 어휘 분석기에 알려줍니다)

몇 가지를 봅니다.

1. Type Type;금지되어 있습니다. typename으로 선언 된 식별자는 typename이 아닌 식별자 struct Type Type가 될 수 없습니다 (모호하지 않으며 여전히 허용 될 수 있음).

   세 가지 유형이 있습니다 names tokens.

   • types : 내장형 또는 typedef / class / struct로 인해
   • 템플릿 기능
   • 식별자 : 함수 / 방법 및 변수 / 객체

   템플릿 기능을 다른 토큰으로 고려하면 func<모호성이 해결 됩니다. 경우 func템플릿 기능 이름은 다음 <그렇지 않으면 템플릿 매개 변수 목록의 시작해야합니다 func함수 포인터와 <비교 연산자입니다.

2. Type a(2);객체 인스턴스화입니다. Type a();그리고 Type a(int)함수 프로토 타입입니다.

3. int (k); 완전히 금지되어 있어야합니다. int k;

4. typedef int func_type();및 typedef int (func_type)();금지된다.

   A function typedef must be a function pointer typedef : typedef int (*func_ptr_type)();

5. template recursion is limited to 1024, otherwise an increased maximum could be passed as an option to the compiler.

6. int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); could be forbidden too, replaced by int a,b,c[9],*d; int (*f)();

   int (*g)()[9];

   int h(char);

   one line per function prototype or function pointer declaration.

   An highly preferred alternative would be to change the awful function pointer syntax,

   int (MyClass::*MethodPtr)(char*);

   being resyntaxed as:

   int (MyClass::*)(char*) MethodPtr;

   this being coherent with the cast operator (int (MyClass::*)(char*))

7. typedef int type, *type_ptr; could be forbidden too : one line per typedef. Thus it would become

   typedef int type;

   typedef int *type_ptr;

8. sizeof int, sizeof char, sizeof long long and co. could be declared in each source file. Thus, each source file making use of the type int should begin with

   #type int : signed_integer(4)

   and unsigned_integer(4) would be forbidden outside of that #type directive this would be a big step into the stupid sizeof int ambiguity present in so many C++ headers

The compiler implementing the resyntaxed C++ would, if encountering a C++ source making use of ambiguous syntax, move source.cpp too an ambiguous_syntax folder, and would create automatically an unambiguous translated source.cpp before compiling it.

Please add your ambiguous C++ syntaxes if you know some!

---

As you can see in my answer here, C++ contains syntax that cannot be deterministically parsed by an LL or LR parser due to the type resolution stage (typically post-parsing) changing the order of operations, and therefore the fundamental shape of the AST (typically expected to be provided by a first-stage parse).

---

I think you are pretty close to the answer.

LR(1) means that parsing from left to right needs only one token to look-ahead for the context, whereas LR(∞) means an infinite look-ahead. That is, the parser would have to know everything that was coming in order to figure out where it is now.

---

The "typedef" problem in C++ can be parsed with an LALR(1) parser that builds a symbol table while parsing (not a pure LALR parser). The "template" problem probably cannot be solved with this method. The advantage of this kind of LALR(1) parser is that the grammar (shown below) is an LALR(1) grammar (no ambiguity).

/* C Typedef Solution. */

/* Terminal Declarations. */

   <identifier> => lookup();  /* Symbol table lookup. */

/* Rules. */

   Goal        -> [Declaration]... <eof>               +> goal_

   Declaration -> Type... VarList ';'                  +> decl_
               -> typedef Type... TypeVarList ';'      +> typedecl_

   VarList     -> Var /','...     
   TypeVarList -> TypeVar /','...

   Var         -> [Ptr]... Identifier 
   TypeVar     -> [Ptr]... TypeIdentifier                               

   Identifier     -> <identifier>       +> identifier_(1)      
   TypeIdentifier -> <identifier>      =+> typedefidentifier_(1,{typedef})

// The above line will assign {typedef} to the <identifier>,  
// because {typedef} is the second argument of the action typeidentifier_(). 
// This handles the context-sensitive feature of the C++ language.

   Ptr          -> '*'                  +> ptr_

   Type         -> char                 +> type_(1)
                -> int                  +> type_(1)
                -> short                +> type_(1)
                -> unsigned             +> type_(1)
                -> {typedef}            +> type_(1)

/* End Of Grammar. */

The following input can be parsed without a problem:

 typedef int x;
 x * y;

 typedef unsigned int uint, *uintptr;
 uint    a, b, c;
 uintptr p, q, r;

The LRSTAR parser generator reads the above grammar notation and generates a parser that handles the "typedef" problem without ambiguity in the parse tree or AST. (Disclosure: I am the guy who created LRSTAR.)

참고URL : https://stackoverflow.com/questions/243383/why-cant-c-be-parsed-with-a-lr1-parser