파서 레퍼런스

파서의 목적은 문법에 부합하는 토큰 문자열을 인식하고, 선택적으로 이를 다른 것으로 변환하는 것입니다.

파서 섹션

파서 선언은 @parser 키워드로 시작하는 파서 섹션에 포함됩니다.

@parser

// 파서 선언

규칙

파서 규칙은 파서의 기본 구성 요소입니다. 터미널(토큰)과 비터미널(다른 규칙)의 변환을 정의하며, 재귀적으로 다른 규칙 프로덕션의 항으로 참조될 수 있습니다. 파서 규칙 구문은 확장 백커스-나우르 형식 (EBNF)과 유사합니다.

Lox 규칙 구문 자체를 Lox로 간결하게 표현할 수 있습니다:

rule      = '@start'? ID '=' @list(prod, '|') NL
prod      = term_card+ qualif?
          | '@empty'

term_card = term card?
term      = ID | LITERAL | '@error' | list
list      = '@list' '(' term ',' term ')'
card      = '*' | '*!' | '+' | '?'
qualif    = '@left' '(' NUM ')'
          | '@right' '(' NUM ')'

다음 예제 규칙을 자세히 살펴보겠습니다:

prod = term_card+ qualif?
     | '@empty'

• prod는 규칙의 이름입니다.
• term_card+ qualif?와 '@empty'는 규칙의 프로덕션입니다.
• term_card+와 qualif?는 첫 번째 프로덕션의 항입니다.
• term_card와 qualif는 다른 규칙을 참조합니다.
• +는 하나 이상의 term_card가 예상됨을 나타내는 카디널리티입니다. 마찬가지로 ?는 0개 또는 1개의 qualif가 예상됨을 나타냅니다.
• '@empty'는 리터럴 형식으로 참조되는 토큰입니다.

참고사항:

• 규칙 이름은 유효한 Go 식별자여야 하며 다음 추가 제한사항이 있습니다:
  • 밑줄(_)로 시작하면 안 됩니다.
  • 연속된 밑줄을 포함하면 안 됩니다.

줄 연속

규칙은 줄 끝으로 종료됩니다. 줄 연속 백슬래시 \를 사용하여 규칙을 여러 줄로 나눌 수 있습니다. 수직 막대 |가 다음 줄의 첫 번째 토큰일 때는 백슬래시를 생략할 수 있습니다. 이 경우 줄 연속이 암시적입니다.

예를 들어:

term = ID | \
       LITERAL | \
       '@error' | \ 
       list

다음과 동일합니다:

term = ID
     | LITERAL
     | '@error'
     | list

후자 형식을 사용하는 것이 관용적이며, |에서 규칙을 나눌 수 없을 때만 \를 사용합니다.

시작 규칙

하나의 규칙, 그리고 오직 하나의 규칙만이 @start 키워드를 사용하여 루트 또는 시작 규칙으로 표시되어야 합니다. 시작 규칙은 파서의 목표입니다. 파서가 시작 규칙을 리듀스하면 파싱이 성공적으로 완료됩니다.

예제:

@start program = statement*

빈 프로덕션

빈 문자열과 일치하는 프로덕션 - 형식 문법에서 종종 그리스 문자 엡실론(ε)으로 표현됨 - 은 항 대신 @empty 키워드를 사용해야 합니다.

예제:

optional_number = NUMBER | @empty

이 예제에서 optional_number 규칙은 NUMBER 토큰과 일치하거나 아무것도 일치하지 않음(즉, 빈 문자열)으로 리듀스될 수 있습니다.

항 카디널리티

항은 카디널리티 수정자로 주석을 달 수 있으며, 이는 항의 인스턴스가 몇 개 일치될 수 있는지를 결정합니다. 카디널리티는 규칙 내에서 선택적, 반복 또는 필수 패턴을 지정하는 데 사용됩니다.

선택적 (?)

?는 항이 선택적임을 나타냅니다.

예제:

some_rule = some_term?

// Lox가 생성:
some_term? = some_term
           | @empty

하나 이상 (+)

+는 항이 하나 이상 일치될 수 있음을 나타냅니다.

예제:

some_rule = some_term+

// Lox가 생성:
some_term+ = some_term+ some_term
           | some_term

0개 이상 (*)

*는 항이 0개 이상 일치될 수 있음을 나타냅니다.

예제:

some_rule = some_term*

// Lox가 생성:
some_term*  = some_term+?
some_term+? = some_term+
            | @empty
some_term+  = some_term+ some_term
            | some_term

리스트 (@list)

@list(elem, sep)는 항이 sep로 구분되면서 elem을 하나 이상 일치시킬 것임을 나타냅니다.

예제:

some_rule = @list(some_term, ',')

// Lox가 생성:
@list(some_term, ',') = @list(some_term, ',') ',' some_term
                      | some_term

@list는 ?로 추가 수식하여 0개 이상의 요소 리스트와 일치시킬 수 있습니다.

우선순위와 결합성

다음 문법은 모호합니다. 이를 분석하려고 시도하면 grammar has conflicts 오류로 실패합니다:

expr = expr '+' expr
     | expr '*' expr
     | NUMBER

일반적인 설명은 파서 충돌을 참조하세요.

연산자 우선순위와 관련된 충돌은 우선순위와 결합성 수식자를 사용하여 해결할 수 있습니다:

expr = expr '+' expr  @left(1)
     | expr '*' expr  @left(2)
     | NUMBER

문법의 @left 수식자는 lox에게 expr '+' expr와 expr '*' expr 사이의 충돌을 만났을 때 후자가 전자보다 우선순위를 가져야 한다고 알려줍니다.

Lox의 우선순위 수식자는 단일 규칙 내의 모호성을 해결하는 데 사용됩니다. 모호성이 여러 규칙에 걸쳐 있으면 우선순위 수식자는 효과가 없으며, 해결을 위해 문법 리팩토링이 필요할 것입니다.

연산자 우선순위의 충돌을 해결할 때는 연산자의 결합성도 고려하는 것이 중요합니다. 결합성은 괄호가 없을 때 동일한 우선순위 수준의 연산자가 어떻게 그룹화되는지를 결정합니다.

좌결합성 (@left)

덧셈과 뺄셈 같은 좌결합 연산자의 경우, 연산자의 여러 인스턴스가 연속으로 나타날 때 파서는 왼쪽부터 그룹화합니다.

예제:

expr = expr '+' expr  @left(1)
     | NUMBER

입력 1 + 2 + 3이 주어지면 파서는 다음과 같이 처리합니다:

(1 + 2) + 3

이는 @left 수식자 때문이며, 이는 파서가 다음을 고려하기 전에 첫 번째 expr을 리듀스하게 합니다.

우결합성 (@right)

거듭제곱이나 할당 같은 우결합 연산자의 경우, 파서는 오른쪽부터 표현식을 그룹화합니다.

예제:

expr = expr '^' expr  @right(1)
     | NUMBER

입력 2 ^ 3 ^ 4의 경우, 파서는 다음과 같이 그룹화합니다:

2 ^ (3 ^ 4)