이 XML 하위 집합에 대해 LL (1) 문법이 있습니까?

Question

나는 다음과 같은 EBNF 문법과 XML의 가상의 부분 집합에 대한 파서를 만들려고 해요 : 변경없이 '있는 그대로'

DOCUMENT ::= ELEMENT 
ELEMENT ::= START_TAG (ELEMENT | DATA)* END_TAG | EMPTY_TAG 
START_TAG ::= < NAME ATTRIBUTE* > 
END_TAG ::= </ NAME > 
EMPTY_TAG ::= < NAME ATTRIBUTE* /> 
ATTRIBUTE ::= NAME = STRING 

것은 위의 문법이다.

DOCUMENT   ::= ELEMENT EOF 
ELEMENT   ::= PREFIX > ELEMENT_OR_DATA END_TAG 
         | PREFIX /> 
PREFIX   ::= < NAME OPT_ATTR 
ELEMENT_OR_DATA ::=  OPT_ELEMENT ELEMENT_OR_DATA 
         | OPT_DATA ELEMENT_OR_DATA 
         | epsilon 
OPT_ELEMENT  ::= ELM_LIST | epsilon 
ELM_LIST   ::= ELEMENT | ELEMENT ELM_LIST 
OPT_DATA   ::= DATA_LIST | epsilon 
DATA_LIST  ::= DATA | DATA DATA_LIST 
END_TAG   ::= </ NAME > 
OPT_ATTR   ::= ATTR_LIST | epsilon 
ATTR_LIST  ::= ATTRIBUTE | ATTRIBUTE ATTR_LIST 
ATTRIBUTE  ::= NAME = STRING 
EOF    ::=   &$ 

원래의 LL (1) 버전입니다 : 은 여기에 (1) LL로 변환 나의 시도인가? 그렇지 않다면 어디서 잘못 되었습니까? 그렇다면 의미를 바꾸지 않고 '단순화'할 방법이 있습니까? 나는 내가 가능한 가장 간단한 버전을 가지고 있다고 확신하지 않는다.

희망이 있습니다.

Answer 1

LL (1) 파서는 다음 토큰을 살펴 봄으로써 ELEMENT의 두 규칙에 대한 올바른 규칙을 선택할 수 없습니다. 문법에 따르면, 파서는 첫 번째 규칙 시도해야합니다 : ELEMENT ::= PREFIX > ELEMENT_OR_DATA END_TAG 을 그리고 그것은 작동하지 않을 경우, 그것은 두 번째 규칙 시도하기 위해 재귀 (역행)에서 반환해야합니다 : 이 ELEMENT ::= PREFIX />

문제는이다 두 규칙 모두 동일한 "개체"PREFIX에서 시작됩니다. 이 경우 터미널이 아니기 때문에 "악화"가됩니다.

확실히 LL (1) 문법이 아닙니다. 하나 만들어 보자.

우리는 첫 번째 태그의를 제거하여 원래의 문법을 단순화 : DOCUMENT ::= ELEMENT ELEMENT ::= < NAME ATTRIBUTE* > (ELEMENT | DATA)* </ NAME > ELEMENT ::= < NAME ATTRIBUTE* /> ATTRIBUTE ::= NAME = STRING

다음 단계는 올바른 규칙을 선택하는 파서에 도움이됩니다 첫 번째 토큰을 얻기 위해 요소에 대한 규칙을 분할하는 것입니다. DOCUMENT ::= ELEMENT ELEMENT ::= < NAME ATTRIBUTE* ELEMENT1 ELEMENT1 ::= > (ELEMENT | DATA)* </ NAME > ELEMENT1 ::= /> ATTRIBUTE ::= NAME = STRING

이제 파서가 요소 구문 분석을 시작할 수 있습니다. 확장되거나 짧은 요소인지 여부를 결정을 "연기"하고이 질문을 ELEMENT1 규칙에 위임합니다. 나중에 다음 토큰이 > 또는 />인지 확인하여 구문 분석중인 요소 유형을 판별 할 수 있습니다.

이의이 변화를 계속하자 : DOCUMENT ::= ELEMENT ELEMENT ::= < NAME ATTRIBUTES ELEMENT1 ELEMENT1 ::= > ELEMENT_OR_DATA </ NAME > ELEMENT1 ::= /> ELEM_OR_DATA ::= ELEMENT ELEM_OR_DATA ELEM_OR_DATA ::= DATA ELEM_OR_DATA ELEM_OR_DATA ::= epsilon ATTRIBUTES ::= NAME = STRING ATTRIBUTES ATTRIBUTES ::= epsilon

우리는 대체 * 적절한 LL 구문 - 연산자. 이 마지막 문법에는 여전히 문제가 있습니다. 처음 두 개의 ELEM_OR_DATA 규칙은 적용 할 항목을 추측 할 수 없기 때문에 파서를 "혼동"시킬 수 있습니다 (처음에 설명한 문제와 비슷한 문제).

는의 파서에 대한 힌트를 제공함으로써이 문제를 해결하자 DOCUMENT ::= ELEMENT EOF ELEMENT ::= < ELEMENT0 ELEMENT0 ::= NAME ATTRIBUTES ELEMENT1 ELEMENT1 ::= > ELEMENT_OR_DATA </ NAME > ELEMENT1 ::= /> ELEM_OR_DATA ::= < ELEMENT0 ELEM_OR_DATA ELEM_OR_DATA ::= DATA ELEM_OR_DATA ELEM_OR_DATA ::= epsilon ATTRIBUTES ::= NAME = STRING ATTRIBUTES ATTRIBUTES ::= epsilon

우리는 Element1이를 갈라 첫 번째 ELEM_OR_DATA 규칙에 ELEMENT0을 사용했다. 이제 DATA가 토큰이라고 가정하면 파서는 다음 토큰 만보고 적용 할 규칙을 쉽게 결정할 수 있습니다.