LL (1) 구문 분석 표의 $ column 아래 항목이 필요합니까?

Question

프로그래밍 언어의 LL (1) 문법에 대한 구문 분석 표에서 $에 대한 열 아래에 항목을 하나 이상 가져와야합니다.

예인 경우 Google의 문법에서 가능한 오류를 찾아 낼 수 있습니다.

Answer 1

$ (입력 끝) 열이 비어있을 수 있습니다. 이런 일이 발생하는 문법의 한 클래스는 S의 모든 제작물이 비어 있지 않고 터미널에서 끝나는 곳입니다.

더 명시 적으로의이 S -> (S*)의 예를 들어 보자, 또는 :

1. S -> (T)
2. T -> S T
3. T -> ε

우리는이 문법에 대해 다음 LL (1) 파싱 테이블을 구축 할 수 있습니다 :

| (  | ) | $ | 
---+---------+-----+-----+ 
S | (T) |  |  | 
T | S T | ε |  | 

LL 파서 스택에는 터미널과 비 터미널이 포함됩니다. 입력 및 스택이 동일한 터미널로 시작되면 스택과 스택이 모두 제거됩니다. 입력이 끝날 때 (특수 터미널로 자주 사용됩니다) 파싱은 성공적으로 완료되었습니다. 입력이 끝나고 파서 스택이 비어있는 경우에만 구문 분석이 성공적으로 완료되었습니다.

제가 생각할 수있는 $ 열에 대한 유일한 현명한 입력은 ε입니다. 결국 스택에 비어 있지 않은 터미널이 있으면 빈 문자열을 구문 분석하는 것은 불가능합니다. $ 열에 일부 터미널에 대해 ε이 포함되어 있으면 입력이 끝났을 때 스택에서 해당 열을 제거 할 수 있음을 의미합니다. 예를 들어, 우리는 이것을 허용 할 이유가 없습니다.