문맥 자유 문법을 사용하여 모호한 문을 찾습니다.

Question

성명이 정의 된 문법이 주어지면 문안의 모호성을 감지 할 수있는 숙제가 있습니다.

예 : 두 개의 구문 분석 트리가 가능하기 때문에

Grammar: S -> S + S | S * S | id 
Statement: id * id + id 

위의 문은 모호합니다.

지금 현재의 마음에 다음과 같은 모호성을 가지고 :

1) Operator precedence (example above) 
2) If-else dangling case 
3) Infinite loop (example above is left recursive) 
4) Associativity

당신이 행할 수있을 것이다 더 이상 말해 줄 수 있을까요?

필자는 lex와 bison (yacc)을 사용하여이 파서를 디자인하고 2 일 후에 제출해야하므로 모든 포인터가 문법과 명령문의 모호성에 도움이됩니다.

Answer 1

음, 명령에 lex와 bison이 있으면 간단히 문법을 들소에 넣을 수 있으며 모호한 지 여부를 알려줍니다.

그렇지 않으면 문법이 모호하게 만드는 충돌이 있는지 확인하기 위해 전체 LALR1 파서 생성기 알고리즘을 구성해야합니다. 이러한 충돌은 파서 작성 단계에서 꽤 늦게 발견됩니다 (파서 생성기는 테이블 생성 단계에서 파서 생성자를 찾습니다). 아마도 당신은 내 코드가 수행하는 코드에서 어떤 포인터를 취할 수 있습니다. https://github.com/Dervall/Piglet

동작의 일부를 채우려 고 할 때 아래쪽 위로있는 구문 분석기의 shift/reduce 및 reduce/reduce의 고전적인 경우가 발생합니다 테이블에 넣으려고하는 토큰과 우선 순위가 동일한 항목이 이미 채워져 있습니다.

LL 파서에 대해 이야기하는 경우, 무한 루프는 실제로 애매한 문법의 사례가 아닙니다. 문법은 애매 모호하지 않게 리팩터링 될 수 있습니다.

문구 자체가 어떤 방식 으로든 문법에 모호하지 않습니다. 입력 내용에 상관없이 모호했습니다.

Answer 2

일반적으로 문법의 모호성은 undecidable입니다.

즉, 분명히 모호한 문법 패턴이 많이 있습니다.

• 왼쪽과 오른쪽 모두 재귀적인 (비 쓸모없는) 비 단말기는 모호합니다 (다른 사람이 매달린 경우를 제외하고 위에서 언급 한 모든 사례를 다룹니다).
• 두 개의 오른쪽 재귀 규칙 중 하나가 다른 하나의 접두사 인 (비 쓸모없는) 비 터미널은 모호합니다 (dangling-else를 포함).