LR (1) 문법의 정의에서 모호성을 해결하는 방법은 무엇입니까?

Question

OCaml에 Golang 컴파일러를 쓰고 있는데, 인수 목록이 나에게 약간의 골칫거리가되고 있습니다.

func g(int, string, int) 

두 가지 스타일이 될 수 없습니다 : 매개 변수 이름없이 또한 유형의 목록을 가질 수

func f(a, b, c int) === func f(a int, b int, c int) 

: 이동, 당신은 다음과 같은 방법으로 같은 유형의 그룹 연속 매개 변수 이름을 수 믹스 앤 매치; 모든 매개 변수가 명명되었거나 없음입니다.

내 문제는 파서가 쉼표를 볼 때 무엇을 해야할지 모르기 때문입니다. 첫 번째 예제에서는 a이 더 많은 변수가있는 변수의 이름 또는 유형의 이름입니까? 쉼표는 이중 역할을 가지고 있으며이를 해결하는 방법을 모르겠습니다.

OCaml 용 Menhir 파서 생성기 도구를 사용하고 있습니다.

편집 : 당신은 모호성이없는 http://golang.org/ref/spec#Function_types

Answer 1

작성한대로 go 문법은 LALR(1)이 아닙니다. 실제로 k에 대해서는 LR(k)이 아닙니다. 그러나 명확히 알 수 있듯이 GLR 파서를 사용하여 파서를 성공적으로 파싱 할 수 있습니다 (OCAML에 대한 GLR 파서 생성기가 여러 개있는 것은 확실하지만 그 중 일부에 대해서는 충분히 알지 못합니다). 하나 추천).

GLR 파서를 사용하고 싶지 않거나 사용하지 않으려면 gccgo 컴파일러에서 Russ Cox가 수행 한 방식과 동일하게 수행 할 수 있습니다.이 컴파일러는 bison을 사용합니다. (bison은 GLR 파서를 생성 할 수 있지만 Cox는이 기능을 사용하지 않습니다.) 그의 기술은 유형 이름과 유형이 아닌 이름을 구별하는 스캐너에 의존하지 않습니다.

오히려, 그냥 요소가 매개 변수 목록을 받아들 name_or_type 또는 name name_or_type (실제로,이보다 더 많은 가능성이 있기 때문에 ... 구문의,하지만 그것은 일반적인 원칙을 변경하지 않습니다.) 즉, 모호, 간단하고 예를 들어 func foo(a, b int, c)을 받아 들일 것이며, 선언 된 매개 변수 목록에 유형을 첨부하지 않기 때문에 올바른 추상 구문 트리를 생성하지 못합니다.

이것은 일단 인수 목록이 완전히 구문 분석되고 일부 함수 선언 (예 :)에 첨부 된 AST에 삽입되면 의미 픽스를 수행하여이를 수정하고 필요한 경우 생성합니다 오류 메시지. 이 검색은 선언 요소 목록에서 오른쪽에서 왼쪽으로 수행되므로 지정된 유형을 왼쪽으로 전파 할 수 있습니다.

참조 설명서의 문법 또한 "모든 매개 변수의 이름이 지정되었거나 지정되지 않았습니다."라는 제약 조건을 나타내지 않으므로 지나치게 받아들입니다. 그 제약 조건 은으로 LR (1) 문법으로 표현할 수 있습니다. 독자의 연습 문제로 남겨 두겠습니다. 그러나 결과 문법은 이해하기가 훨씬 어려울 것입니다.

Answer 2

에 지정된 순간에, 내 선돌 문법은 정확히 규칙을 따른다. 표준 Go 파서가 LALR (1)이라는 사실은 그것을 증명합니다.

은 더 많은 변수가있는 변수의 유형 또는 이름의 이름입니까?

기본적으로 문법과 파서는 전체적으로 기호 테이블에서 완전히 분리되어야합니다. do not C – 문법이 모호하지 않으므로 나중에 AST에서 유형 이름을 확인할 수 있습니다.

다음은 관련 규칙입니다 (http://golang.org/ref/spec). 그들은 이미 맞습니다.

Parameters  = "(" [ ParameterList [ "," ] ] ")" . 
ParameterList = ParameterDecl { "," ParameterDecl } . 
ParameterDecl = [ IdentifierList ] [ "..." ] Type . 
IdentifierList = identifier { "," identifier } . 

내가 당신에게 설명 할 것이다 :

IdentifierList = identifier { "," identifier } . 

중괄호은 (는 별표의 POSIX 정규 표현식 표기)를 kleene 폐쇄를 나타냅니다.

ParameterDecl = [ IdentifierList ] [ "..." ] Type . 

대괄호

이 널 (NULL)입니다,이 규칙은 "광고 인해서 식별자 이름은 임의로 리터럴 쉼표와 식별자 등 중 & hellip 다음, 리터럴 쉼표와 식별자 다음에"라는; 이는 해당 부분이 존재할 수도 있고 존재하지 않을 수도 있음을 의미합니다. (POSIX 정규식 표기법에서 이것은 의문의 대상이다). 그래서 당신은 "이 어쩌면 유형 다음에 아마 생략 부호 다음에 여기서 identifierList,.

ParameterList = ParameterDecl { "," ParameterDecl } . 

당신은 예를 들어 func x(a, b int, c, d string) 같은 목록에 여러 ParameterDecl 수 있습니다.

Parameters  = "(" [ ParameterList [ "," ] ] ")" . 

이 규칙은 것을 정의 parameterList에 선택적 괄호로 묶어야하는 것입니다 그리고 당신은 같은 것을 쓸 때, 문자 그대로의 유용한 옵션 최종 쉼표를 포함 할 수있다 :

func x(
    a, b int, 
    c, d string, // <- note the final comma 
) 

의 이동 미국 서부 및 서남부에서 자라는 목초를 r은 휴대용이며 lookahead 토큰 하나를 사용하여 상향식 파서로 구문 분석 할 수 있습니다.

---

은 관련 편집 "C를하지 말라":이 C is context-sensitive 길 때문에 많은 (? 모두) 컴파일러에서이 문제를 렉서 및 렉싱에 심볼 테이블을 연결하여되고 해결했다 토큰은 형식 이름이나 변수로 정의되는지 여부에 따라 다르게 적용됩니다. 이것은 해킹이며 모호하지 않은 문법을 위해 수행되어서는 안됩니다!