C++를 LR(1) 구문 분석기로 구문 분석할 수 없는 이유는 무엇입니까?
https://stackoverflow.com/questions/243383
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 파서와 파서 생성기에 대해 읽고 있었고 wikipedia의 LR parsing 페이지에서 다음 문장을 발견했습니다.
LR 파서의 일부 변형을 사용하여 많은 프로그래밍 언어를 구문 분석할 수 있습니다.주목할만한 예외 중 하나는 C++입니다.
왜 그래야만하지?C++의 어떤 특별한 속성으로 인해 LR 파서로 구문 분석이 불가능합니까?
Google을 사용하여 C는 LR(1)로 완벽하게 구문 분석할 수 있지만 C++에는 LR()이 필요하다는 사실만 발견했습니다.
해결책
흥미로운 스레드가 있습니다 람다 궁극 그것은 논의합니다 C ++ 용 LALR 문법.
A에 대한 링크가 포함되어 있습니다 박사 학위 논문 여기에는 C ++ 구문 분석에 대한 논의가 포함되며, 여기에는 다음과 같은 설명이 포함됩니다.
"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 ;
두 가지 다른 구문 분석이 있습니다.
- x 유형에 대한 포인터로 y를 선언할 수 있습니다.
- x와 y의 곱이 될 수 있으며 답을 버릴 수 있습니다.
이제 당신은 후자가 어리석고 무시되어야 한다고 생각할 수도 있습니다.대부분은 당신의 의견에 동의할 것입니다.그러나 부작용이 발생할 수있는 경우가 있습니다 (예 : 곱하기가 과부하 된 경우).하지만 그게 요점이 아닙니다.요점은 거기에 있습니다 ~이다 두 가지 다른 구문 분석, 따라서 프로그램은 이것이 어떻게 다른지에 따라 다른 것을 의미 할 수 있습니다. ~해야 한다 구문 분석되었습니다.
컴파일러는 적절한 상황에서 적절한 것을 받아들여야 하며, 다른 정보(예: x 유형에 대한 지식)가 없는 경우 나중에 무엇을 할지 결정하기 위해 두 가지를 모두 수집해야 합니다.따라서 문법은 이것을 허용해야 합니다.그리고 그것은 문법을 모호하게 만듭니다.
따라서 순수 LR 구문 분석으로는 이를 처리할 수 없습니다.Antlr, JavaCC, YACC 또는 전통적인 Bison이나 심지어 PEG 스타일 파서와 같이 널리 사용되는 다른 많은 파서 생성기도 "순수한" 방식으로 사용할 수 없습니다.
더 복잡한 경우가 많이 있습니다(템플릿 구문 분석에는 임의의 예측이 필요한 반면 LALR(k)는 대부분의 k 토큰을 미리 볼 수 있음). 그러나 단 하나의 반례만 사용하면 됩니다. 순수한 LR(또는 기타) 구문 분석.
가장 실제 C/C ++ 파서는 추가 해킹으로 일종의 결정적인 파서를 사용 하여이 예제를 처리합니다.그들은 Symbol Table Collection과 구문 분석 ...따라서 "X"가 발생할 때까지 파서는 X가 유형인지 아닌지를 알고 있으므로 두 잠재적 구문 분석을 선택할 수 있습니다.그러나이 작업을 수행하는 파서는 컨텍스트가 없으며 LR 파서 (순수한 파서 등)는 (최대) 컨텍스트가 없습니다.
이 명확성을 수행하기 위해 LR 파서에 RUL 당 감소 시간 시맨틱 점검을 추가 할 수 있습니다.(이 코드는 종종 간단하지 않습니다.)다른 파서 유형의 대부분은 구문 분석의 다양한 지점에서 시맨틱 점검을 추가 할 수있는 수단이 있으며,이를 수행하는 데 사용할 수 있습니다.
그리고 충분히 속임수를 찍으면 LR 파서가 C 및 C ++에서 작동하도록 할 수 있습니다.GCC 직원들은 잠시 동안했지만 손으로 코딩 된 구문 분석을 위해 포기했습니다. 나는 그들이 더 나은 오류 진단을 원했기 때문에 생각합니다.
그래도 다른 접근법이 있습니다.이 접근법은 훌륭하고 깨끗하며 C 및 C ++는 심볼 테이블 해커없이 잘 정밀합니다. GLR 파서.이들은 완전한 컨텍스트 자유 파서입니다 (효과적으로 무한한 룩 그는).GLR 파서는 단순히 수락합니다. 둘 다 구문 분석, "트리"(실제로는 대부분의 트리와 같은 지시 된 acyclic 그래프)를 생성하는 모호한 구문 분석을 나타냅니다.사후 분석 패스를 통해 모호성을 해결할 수 있습니다.
우리는 DMS 소프트웨어 리엔지니어링 테이크 (DESTINT TOKE) 에이 기술을 C 및 C ++ 프론트 엔드에서 사용합니다 (2017 년 6 월 현재 MS 및 GNU 방언의 전체 C ++ 17을 처리합니다).이들은 소스 코드의 완전한 세부 사항을 갖춘 AST를 생성하는 완전하고 정확한 구문 분석과 함께 수백만 개의 대형 C 및 C ++ 시스템을 처리하는 데 사용되었습니다.(보다 C++의 가장 까다로운 구문 분석을 위한 AST입니다.)
문제는 이와 같이 정의되지는 않지만 흥미로워 야합니다.
이 새로운 문법이 "컨텍스트가없는"YACC 파서에 의해 완벽하게 구문 분석 될 수 있도록 C ++ 문법에 대한 가장 작은 수정 세트는 무엇입니까? (하나의 '해킹'만 사용 : 타이프 이름/식별자 명확성, 파서는 모든 typedef/class/struct의 Lexer에게 알려줍니다)
나는 몇 가지를 본다 :
Type Type;금지되어 있습니다. 타이프 이름으로 선언 된 식별자는 유형이 아닌 이름 식별자가 될 수 없습니다 (struct Type Type모호하지 않으며 여전히 허용 될 수 있습니다).3 가지 유형이 있습니다
names tokens:types: 내장형 유형 또는 typedef/class/struct 때문에- 템플릿 기능
- 식별자 : 기능/방법 및 변수/객체
템플릿 기능을 다른 토큰으로 고려하면 해결됩니다
func<모호. 만약에func그렇다면 템플릿 기능 이름입니다<템플릿 매개 변수 목록의 시작 여야합니다.func기능 포인터입니다<비교 연산자입니다.Type a(2);객체 인스턴스화입니다.Type a();그리고Type a(int)기능 프로토 타입입니다.int (k);완전히 금지되어 있어야합니다int k;typedef int func_type();그리고typedef int (func_type)();금지되어 있습니다.function typedef는 함수 포인터 typedef 여야합니다.
typedef int (*func_ptr_type)();템플릿 재귀는 1024로 제한되며, 그렇지 않으면 증가 된 최대 값은 컴파일러 옵션으로 전달 될 수 있습니다.
int a,b,c[9],*d,(*f)(), (*g)()[9], h(char);금지 될 수 있습니다int a,b,c[9],*d;int (*f)();int (*g)()[9];int h(char);기능 프로토 타입 또는 기능 포인터 선언 당 하나의 라인.
매우 선호되는 대안은 끔찍한 기능 포인터 구문을 변경하는 것입니다.
int (MyClass::*MethodPtr)(char*);다음과 같이 재 동성.
int (MyClass::*)(char*) MethodPtr;이것은 캐스트 연산자와 일치합니다
(int (MyClass::*)(char*))typedef int type, *type_ptr;금지 될 수 있습니다 : typedef 당 하나의 줄. 따라서 그것은 될 것입니다typedef int type;typedef int *type_ptr;sizeof int,sizeof char,sizeof long long그리고 공동. 각 소스 파일에서 선언 할 수 있습니다. 따라서 각 소스 파일은 유형을 사용합니다.int시작해야합니다#type int : signed_integer(4)그리고
unsigned_integer(4)그 밖에서 금지 될 것입니다#type지침 이것은 바보 같은 큰 발걸음이 될 것입니다sizeof int많은 C ++ 헤더에 모호성이 있습니다
recyntaxed c ++를 구현하는 컴파일러는 모호한 구문을 사용하여 C ++ 소스를 만나면 움직입니다. source.cpp 너무 ambiguous_syntax 폴더 및 모호하지 않은 번역을 자동으로 생성합니다 source.cpp 컴파일하기 전에.
알고 있다면 모호한 C ++ 구문을 추가하십시오!
내에서 볼 수 있듯이 여기서 답하십시오, C ++에는 유형 해상도 단계 (일반적으로 사후 파싱)로 인해 LL 또는 LR 파서에 의해 결정적으로 구문 분석 할 수없는 구문이 포함되어 있습니다. 운영 순서, 따라서 AST의 기본 모양 (일반적으로 1 단계 구문 분석에 의해 제공 될 것으로 예상).
나는 당신이 대답에 매우 가깝다고 생각합니다.
LR (1)은 왼쪽에서 오른쪽으로 구문 분석이 컨텍스트를 보는 데 하나의 토큰 만 필요하지만 LR (∞)은 무한한 외관을 의미합니다. 즉, 파서는 현재 위치를 알아 내기 위해 오는 모든 것을 알아야 할 것입니다.
C ++의 "typedef"문제는 구문 분석 중 (순수한 LALR 파서가 아님) 기호 테이블을 작성하는 LALR (1) 파서로 구문 분석 할 수 있습니다. "템플릿"문제는 아마도이 방법으로 해결할 수 없을 것입니다. 이러한 종류의 LALR (1) 파서의 장점은 문법 (아래 표시)이 LALR (1) 문법 (모호성 없음)이라는 것입니다.
/* 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. */
다음 입력은 문제없이 구문 분석 할 수 있습니다.
typedef int x;
x * y;
typedef unsigned int uint, *uintptr;
uint a, b, c;
uintptr p, q, r;
그만큼 LRSTAR PARSER 생성기 위의 문법 표기법을 읽고 구문 분석 트리 또는 AST에서 모호성없이 "typedef"문제를 처리하는 구문 분석기를 생성합니다. (공개 : 나는 lrstar를 만든 사람입니다.)
