이 LL (1) 파서를 LL (k) 파서에 적용하는 방법은 무엇입니까?

Question

드래곤 북의 부록에서 LL (1) 프런트 엔드가 예제로 제공되었습니다. 나는 그것이 매우 도움이된다고 생각한다. 그러나 아래의 문맥 자유 문법에 대해서는 적어도 LL (2) 파서가 필요하다는 것을 알게되었습니다.

statement : variable ':=' expression 
      | functionCall 

functionCall : ID'(' (expression (',' expression)*)? ')' 
      ; 
variable : ID 
     | ID'.'variable 
     | ID '[' expression ']' 
     ; 

어떻게하면 LL (1) 파서가 k 미리보기 토큰을 지원하도록 렉서를 조정할 수 있습니까? 우아한 방법이 있습니까?

토큰 용 버퍼를 추가 할 수 있습니다. 프로그래밍에 대해 자세히 설명하고 싶습니다.

---

이

은 파서입니다 :

class Parser 
{ 
    private Lexer lex; 
    private Token look; 
    public Parser(Lexer l) 
    { 
     lex = l; 
     move(); 
    } 

    private void move() 
    { 
     look = lex.scan(); 
    } 
} 

---

과 Lexer.scan() 스트림에서 다음 토큰을 반환합니다.

Answer 1

LL(k) 구문 분석을 수행하려면 실제로는 k lookahead 토큰을 버퍼해야합니다. k이 2이면 다른 개인 회원 look2 또는 일부를 사용하여 look에 하나의 토큰을 버퍼링하는 현재 방법을 확장하면됩니다. k의 경우 링 버퍼를 사용할 수 있습니다.

실제로는 항상 전체 미리보기가 필요하지 않습니다. 대부분의 경우, 하나의 토큰 미리보기만으로 충분합니다. 코드를 의사 결정 트리로 구성해야하며, 향후 토큰은 모호성을 해결하는 데 필요한 경우에만 참조됩니다. (종종 "알 수없는"특별한 토큰 유형을 제공하는 것이 유용합니다.이 토큰 유형은 버퍼 된 토큰 목록에 지정되어 미리보기가 그 지점에 아직 도달하지 못했음을 나타낼 수 있습니다.) 또는 대체로 항상 미리보기 토큰을 유지할 수 있습니다.

또는 대체 방법을 하나만 사용하고 구문 분석 오류를보고하는 대신 작동하지 않는 대체 구문을 사용할 수 있습니다. 파서와 렉서의 상태를 복원하십시오 다음 대안으로. 이 모델에서 렉서는 현재 입력 버퍼 위치를 명시 적 인수로 취하며 입력 버퍼는 다시 불러올 수 있어야합니다. 그러나 미리보기 버퍼를 사용하면 렉서 기능을 효과적으로 메모 할 수 있으므로 되감기 및 다시 검색을 피할 수 있습니다. (당신이 당신의 프로파일 링이 유용 할 것이라고 표시 할 때까지 코드의 복잡성을 추가 연기 할 수 있도록 스캔, 일반적으로 가끔 재 스캔 문제가되지 않는 빠른 충분하다.)

두 노트 :

1) 나 ' 규칙에 대해 회의 m :

functionCall : ID'(' (expression (',' expression)*)* ')' 
      ; 

예를 들어, 수 것 :

바로 나에게 보이지 않는

function(a[3], b[2] c[x] d[y], e.foo) 

. 일반적으로 ()의 내용을 (선택 사항) 대신 (선택 사항)으로 표시합니다. 선택 마커 사용 ?대신 초 149) 클린의 별 (Kleene star *의 :

functionCall : ID'(' (expression (',' expression)*)? ')' 
      ; 

2) 제 생각에는, 당신은 정말, 상향식 (bottom-up) 식의 언어에 대한 구문 분석을 사용하여 생성 된 LR(1) 파서 또는 수작업으로 제작 프랫 파서 중 하나를 고려해야한다 . LL(1)은 거의 적합하지 않습니다. 물론 파서 생성기를 사용하는 경우 효과적으로 LL(∞)을 구현하는 ANTLR과 같은 도구를 사용할 수 있습니다. 당신을위한 선견지배를 처리 할 것입니다.