문제를 해결 shift-충돌을 감소에 문법

Question

를 쓰려고 노력해요 작은 파서 아이러니.불행하게도 내가"shift-충돌을 감소하".문법은 내 강점,그리고 나만을 얻을 필요 이 하나의 작은 곳다.여기에 감소한 문법을 생산하는 오류:

ExpressionTerm := "asd"
LogicalExpression :=
    ExpressionTerm |
    LogicalExpression "AND" LogicalExpression |
    LogicalExpression "OR" LogicalExpression

무엇"shift-충돌을 감소"를 의미하고 어떻게 할 수 있습니다.내가 수집하는 것을 의미 내의 문법이 모호하지만,트위스트 나의 논리에 충분하는 방법을 참조하십시오.

추가: 을 명확히-"asd"는 단순히 문자열"asd".그래서 저는 다음과 같은 표현되 이 문법:

asd
asd AND asd
asd AND asd OR asd
asd OR asd AND asd OR asd

추가 2: 할 말을 잊었,의 근본 문법 LogicalExpression.

추가 3: 아,나는 그것을 얻었다!모호성 때문에 같은 식을

asd AND asd OR asd

해석할 수 있는 두 가지 방법으로:

(asd AND asd) OR asd
asd AND (asd OR asd)

하지만 어떻게 해결할 수 있는 이?OK,I 를 넣을 수 있는 하나의 또는 또는 다른 것보다 더 강한(I had inteded 어쨌든).하지만 지금 보는 오류가 나타납니다 심지어 있는 경우 단지 하나의 연산자입니다.즉,이는 또한 같은 오류가:

LogicalExpression := "asd" | LogicalExpression "OR" LogicalExpression

이 경우에는 내가 이것을 원하는:

asd OR asd OR asd

구문 분석하다.

(asd OR asd) OR asd

는 무엇입 non-모호의 방법으로 이것을 하고 있는가?

추가 4: 그것을 얻었다!

LogicalExpression1 := LogicalExpression1 "OR" LogicalExpression2 | LogicalExpression2
LogicalExpression2 := LogicalExpression2 "AND" LogicalExpression3 | LogicalExpression3
LogicalExpression3 := "NOT" LogicalExpression4 | LogicalExpression4
LogicalExpression4 := "asd" | "(" LogicalExpression1 ")"

이 분석 모든 부 식으로,연산자를 우선 순위가 없는 것으로>과->또는."asd"교체할 수 있으로 표현을 위한 것입니다.

Answer 1

귀하의 문법은 애매한 경우에만 사용 한 예측.을 설명하기 위해 무엇입니까"asd"?그것은 ExpressionTerm 또는습니다.더 보기는 shift-충돌을 감소.내가 의심을 줄-충돌을 감소하도 여기에있다.

대부분의 것(1)/LALR(1)발전기의 제공할 것이 어떤 방법으로 처리하 shift-충돌을 감소를 통해 선행 연산자입니다.대부분의 것입니다 또한 기본적으로 가장 긴 시퀀스에서 존재의 shift-충돌을 감소보다 더 많은,그래서 종종 이러한 무시할 수 있습(후 감시).(이 경우에는 어쩌면 당신이를 이동해야기 하단에 대한 그것이 제대로 작동하).

Answer 2

시프트 레디스 충돌은 문법이 모호하다는 것을 의미합니다. 재귀 규칙으로 토큰 "ASD"는 어느 쪽의 일부로 해석 될 수 있습니다. ExpressionTerm 또는 LogicalExpression 그리고 파서는 어느 것을 결정할 수 없습니다. 넥타이를 깨뜨리려면 추가 규칙이 필요합니다.

Answer 3

교대 감소 갈등은 파서에 관해서는 두뇌를 얻기가 더 어려운 것 중 하나입니다. 갈등을 설명하는 가장 쉬운 방법은이 의사 코드입니다.

if (a) then
   if (b) then
     printf('a + b');
   else
     print('this could be a + !b or !a');

else 문은 첫 번째 또는 두 번째 if에 바인딩 할 수 있습니다. 모호한 문법의 경우 일반적으로 문법의 예상 시프트 reduce 경고의 수를 나타내는 값을 정의합니다.

또는 LL (k) 또는 ll (*) 파서를 사용할 수 있습니다. 이러한 유형의 파서에는 이동/감소 모호성이 없습니다. 응용 프로그램에 따라 LALR (1) 파서보다 쉽거나 어려울 수 있습니다.

Answer 4

문법은 모호합니다 LL(1) 또는 LALR(1) ASD 토큰을 대체 할 수 있기 때문입니다 ExpressionTerm 그리고 또한 LogicalExpression 교대/충돌 감소를 해결하기 위해 문법 규칙을 평평하게합니다.