이것은 모호한 문법입니까? 어떻게 해결해야합니까?

Question

이 서문을 쓰려면 이런 종류의 지식이 필요합니다.

어쨌든 나는 문법이없는 문법을 개발하여 알레그라 표현의 구조를 설명하고 있으므로 CYK 구문 분석 알고리즘의 작동 방식을 스스로 가르쳐줍니다. 그러한 구조가 중위 어 대수식에서만 어떻게 작동하는지 이해하지만 "-"연산자의 단항 및 이진 정의를 처리 할 수있는 문법을 개발하는 방법을 이해할 수 없습니다. 참고로

여기 CNF의 (S는 시작 심볼이다) I 작성한 문법이다 :

S -> X
A -> OS
S -> LB
B -> SR
S -> KS
O -> +
O -> -
O -> *
O ->/
O ->^
K -> -
L -> (
R은 ->) -> KS 및 A -> OS

문제는 어떻게 알고리즘 파싱 CYK 앞서 S 중에서 결정 여부 시간을 알 수 있다는 것이다 "-"연산자를 만나면? 문법이 문맥에서 자유롭습니까? 그리고 가장 중요한 것은 프로그래밍 언어가 바이너리와 단항 빼기 기호 모두로 언어를 처리 할 수 ​​있으므로 어떻게 합리적으로 해석해야합니까?

Answer 1

이 유한 상태 오토마타와 관련된 문제처럼 보인다 내 과정에서 모든 것을 기억하지 않는,하지만 난 OCaml의에 CYK 파서를 작성 그래서 내가 가서 당신이 예를 들어, 당신이 당신의 S -> K S 규칙을 것 3- -4 같은 식을 구문 분석하려는 경우 샷 :

을 취하는 -4 다음 A -> O S 규칙이 - -4을 흡수 할을 소비합니다. 결국 최하위 S 생산 규칙까지 작동합니다. 나열된 A 프로덕션 규칙에 S에서 연결할 수 없으며 일종의 S -> S O S 규칙이 있어야하므로 사용중인 문법에주의해야합니다.

CYK 파싱 알고리즘이 작동하는 방식은 질문에서 언급 한 "사전에 알고 있음"이 아닌 역 추적입니다. CYK 알고리즘은 -4을 S -> K S 규칙으로 구문 분석 한 다음 규칙을 다시 적용하려고 시도합니다.이 생산 규칙은 임의로 긴 단항 체인 -을 허용하기 때문에 다시 적용됩니다. 그러나 알고리즘이 중간 구문 분석 인 3 S을 사용해야한다는 사실을 깨닫게되면 구문 분석에 사용할 수있는 프로덕션 기호가 없다는 것을 알게됩니다. 더 이상 파싱 할 수 없다는 것을 알게되면 다시 돌아가 대신 -을 S -> O S 규칙으로 구문 분석하고 그 즐거운 방법으로 계속 시도합니다.

이것은 문맥에 구애받지 않는 문법은 생산 규칙의 왼쪽에 터미널이 있다는 것을 의미하므로 문법이 그대로 유지된다는 것을 의미합니다. HTH!

Answer 2

문법이 불분명하고 파서가 어떤 경우를 결정할 수 없습니다.

당신은 아마 같은 문법을 사용해야합니다 다음

S -> EXPR 
EXPR -> (EXPR) 
EXPR -> - EXPR 
EXPR -> EXPR + EXPR 
EXPR -> EXPR - EXPR 
// etc... 

Answer 3

대수 표현을 기반으로하는 문법은 모호성을 내기가 다소 어렵습니다. 다음은 해결해야 할 문제의 예입니다.

a + b + c는 자연스럽게 두 개의 구문 분석 트리를 만듭니다. 이 문제를 해결하려면 +의 결합 성의 모호성을 해결해야합니다. 왼쪽에서 오른쪽으로 구문 분석하는 전략이이를 처리하도록 할 수는 있지만주의해야합니다. 지수화는 오른쪽에서 왼쪽으로 연결해야합니다.

a + b * c는 자연스럽게 두 개의 구문 분석 트리를 만듭니다. 이 문제를 해결하려면 운영자 우선 순위를 처리해야합니다.

암시 적 승수 (a + bc)는 허용되는 경우 대부분 토큰 화에서 모든 종류의 악몽을 만듭니다.

단항 빼기는 문제가됩니다.

우리가 이러한 문제를 해결하려고하지만 대수학을 전문으로하는 빠른 구문 분석 문법을 여전히 갖고 있다면 한 가지 접근법은 우선 순위 수준에서 요구되는 바인딩 수준마다 EXPR의 다양한 "수준"을 갖는 것입니다. 일을 종료 할 수 있도록> TERM 등 -> PROD, PROD - -> EXP, EXP SUM : 예를 들어,

TERM -> (S) 
EXPO -> TERM^EXPO 
PROD -> PROD * EXPO 
PROD -> PROD/EXPO 
PROD -> -PROD 
SUM -> SUM + PROD 
SUM -> SUM - PROD 
S -> SUM 

이

당신은 또한 종류의 "홍보"를 허용해야합니다.

희망이 도움이됩니다.