LR, SLR 및 LALR 파서의 차이점은 무엇입니까?

LR, SLR 및 LALR 파서의 차이점은 무엇입니까?

---

LR, SLR 및 LALR 파서의 실제 차이점은 무엇입니까? SLR과 LALR이 LR 파서의 유형이라는 것을 알고 있지만 파싱 테이블에 관한 한 실제 차이점은 무엇입니까?

그리고 문법이 LR, SLR 또는 LALR인지 어떻게 보여줄까요? LL 문법의 경우 구문 분석 테이블의 모든 셀에 여러 생산 규칙이 포함되어서는 안된다는 것을 보여 주면됩니다. LALR, SLR 및 LR에 대한 유사한 규칙이 있습니까?

예를 들어 문법이

S --> Aa | bAc | dc | bda
A --> d

LALR (1)이지만 SLR (1)은 아닙니까?

---

편집 (ybungalobill) : LALR과 LR의 차이점에 대해 만족스러운 답변을 얻지 못했습니다. 따라서 LALR의 테이블은 크기가 더 작지만 LR 문법의 하위 집합 만 인식 할 수 있습니다. 누군가 LALR과 LR의 차이점에 대해 더 자세히 설명해 주시겠습니까? LALR (1) 및 LR (1)은 대답에 충분합니다. 둘 다 1 개의 토큰 미리보기를 사용하며 둘 다 테이블 기반입니다! 어떻게 다릅니 까?

---

SLR, LALR 및 LR 파서는 모두 정확히 동일한 테이블 기반 기계를 사용하여 구현할 수 있습니다.

기본적으로 구문 분석 알고리즘은 다음 입력 토큰 T를 수집하고 현재 상태 S (및 관련 예견, GOTO 및 축소 테이블)를 참조하여 수행 할 작업을 결정합니다.

• SHIFT : 현재 테이블이 토큰 T에서 SHIFT라고 말하면 쌍 (S, T)이 구문 분석 스택으로 푸시되고 현재 토큰에 대해 GOTO 테이블이 말하는 내용에 따라 상태가 변경됩니다 (예 : GOTO (T) ), 또 다른 입력 토큰 T '를 가져오고 프로세스를 반복합니다.
• REDUCE : 모든 상태에는 0, 1 또는 해당 상태에서 발생할 수있는 많은 감소가 있습니다. 구문 분석기가 LR 또는 LALR 인 경우 토큰은 상태에 대한 모든 유효한 감소에 대해 미리보기 세트에 대해 확인됩니다. 토큰이 문법 규칙 G = R1 R2 .. Rn에 대한 감소에 대한 미리보기 세트와 일치하면 스택 감소 및 시프트가 발생합니다. G에 대한 시맨틱 조치가 호출되고 스택이 n (Rn에서) 번 팝되고 쌍 ( S, G)가 스택으로 푸시되고 새 상태 S '가 GOTO (G)로 설정되고주기가 동일한 토큰 T로 반복됩니다. 파서가 SLR 파서 인 경우에는 최대 하나의 감소 규칙이 있습니다. 어떤 축소가 적용되는지 검색하지 않고도 축소 조치를 맹목적으로 수행 할 수 있습니다. SLR 파서 가감소 여부; 이것은 각 주가 그와 관련된 감소의 수를 명시 적으로 기록하는지, 그리고 그 수는 어쨌든 실제로 L (AL) R 버전에 필요합니다.
• 오류 : SHIFT 또는 REDUCE가 모두 불가능하면 구문 오류가 선언됩니다.

그래서 그들이 모두 같은 기계를 사용한다면, 요점은 무엇일까요?

SLR의 가치는 구현의 단순성입니다. 최대 하나가 있기 때문에 가능한 감소 검사를 통해 미리보기 세트를 스캔 할 필요가 없으며, 상태에서 SHIFT 종료가없는 경우 유일한 실행 가능한 조치입니다. 어떤 감소가 적용되는지 구체적으로 상태에 첨부 할 수 있으므로 SLR 구문 분석 기계가이를 찾을 필요가 없습니다. 실제로 L (AL) R 파서는 유용하게 더 큰 언어 집합을 처리하며, 구현할 추가 작업이 너무 적기 때문에 학문적 연습을 제외하고는 아무도 SLR을 구현하지 않습니다.

LALR과 LR의 차이점은 테이블 생성기 와 관련이 있습니다.. LR 파서 생성기는 특정 상태 및 정확한 예측 세트에서 가능한 모든 감소를 추적합니다. 모든 감소가 왼쪽 컨텍스트의 정확한 예측 세트와 연관되는 상태로 끝납니다. 이것은 다소 큰 상태 세트를 작성하는 경향이 있습니다. LALR 파서 생성기는 GOTO 테이블과 축소를위한 룩 헤드 세트가 호환되고 충돌하지 않는 경우 상태를 결합합니다. 이것은 LR이 구별 할 수있는 특정 심볼 시퀀스를 구별 할 수 없다는 대가로 상당히 적은 수의 상태를 생성합니다. 따라서 LR 파서는 LALR 파서보다 더 많은 언어 집합을 파싱 할 수 있지만 훨씬 더 큰 파서 테이블을 가지고 있습니다. 실제로, 상태 머신의 크기를 최적화 할 가치가있는 대상 언어에 충분히 가까운 LALR 문법을 찾을 수 있습니다.

따라서 세 가지 모두 동일한 기계를 사용합니다. SLR은 기계의 작은 부분을 무시할 수 있다는 점에서 "쉬운"것이지만 문제의 가치는 없습니다. LR은 광범위한 언어 집합을 구문 분석하지만 상태 테이블은 상당히 큰 경향이 있습니다. 따라서 LALR이 실용적인 선택이됩니다.

이 모든 것을 말했듯이, GLR 파서 는 더 복잡한 기계를 사용 하지만 정확히 동일한 테이블 (LALR에서 사용하는 더 작은 버전 포함)을 사용하여 문맥 자유 언어를 구문 분석 할 수 있다는 것을 아는 것이 좋습니다. 이것은 GLR이 LR, LALR 및 SLR보다 훨씬 강력하다는 것을 의미합니다. 표준 BNF 문법을 작성할 수 있다면 GLR은 이에 따라 구문 분석합니다. 기계의 차이점은 GLR이 GOTO 테이블 및 / 또는 미리보기 세트간에 충돌이있을 때 여러 구문 분석을 시도한다는 것입니다. (GLR이이 작업을 효율적으로 수행하는 방법은 순전히 천재적이지만이 게시물에는 적합하지 않습니다.)

저에게는 매우 유용한 사실입니다. 나는 프로그램 분석기를 구축하고 코드 변환기와 파서는 필요하지만 "흥미롭지 않다"; 흥미로운 작업은 파싱 된 결과로 수행하는 작업이므로 파싱 후 작업을 수행하는 데 중점을 둡니다. GLR을 사용하면 LALR 사용 가능한 형식으로 들어가기 위해 문법을 해킹하는 것에 비해 상대적으로 쉽게 작동하는 문법을 구축 할 수 있습니다. 이것은 전체 언어를 잘 처리하기 위해 문자 그대로 수천 개의 규칙이 필요한 C ++ 또는 Fortran과 같은 비 학문적 인 언어를 처리하려고 할 때 매우 중요하며, 문법 규칙을 해킹하는 데 평생을 소비하고 싶지 않습니다. LALR (또는 LR)의 한계를 충족합니다.

유명한 예로, C ++는 LALR 파싱을하는 사람들에 의해 파싱하기 매우 어려운 것으로 간주됩니다. C ++는 C ++ 참조 설명서 뒷면에 제공된 거의 모든 규칙을 사용하여 GLR 기계를 사용하여 구문 분석하는 것이 간단합니다. (정확히 그런 파서를 가지고 있으며 바닐라 C ++뿐만 아니라 다양한 벤더 방언도 처리합니다. 이는 실제로 GLR 파서 인 IMHO를 사용하기 때문에 가능합니다.)

[2011 년 11 월 편집 : 모든 C ++ 11을 처리하도록 파서를 확장했습니다. GLR을 사용하면 훨씬 쉽게 할 수 있습니다. 2014 년 8 월 편집 : 이제 모든 C ++ 17을 처리합니다. 고장이 나거나 악화 된 것은 없지만 GLR은 여전히 ​​고양이의 야옹입니다.]

---

LALR 파서는 LR 문법 내에서 유사한 상태를 병합하여 동등한 SLR 문법과 정확히 동일한 크기의 파서 상태 테이블을 생성합니다.이 테이블은 일반적으로 순수한 LR 파싱 테이블보다 훨씬 작은 크기입니다. 그러나 LALR이 되기에는 너무 복잡한 LR 문법의 경우 이러한 병합 상태로 인해 파서 충돌이 발생하거나 원래 LR 문법을 완전히 인식하지 못하는 파서를 생성합니다.

BTW, 여기 MLR (k) 구문 분석 테이블 알고리즘에서 이에 대해 몇 가지 언급합니다 .

추가

짧은 대답은 LALR 파싱 테이블이 더 작지만 파서 기계는 동일하다는 것입니다. 주어진 LALR 문법은 많은 중복 (거의 동일) 상태로 모든 LR 상태가 생성되는 경우 훨씬 더 큰 구문 분석 테이블을 생성합니다.

LALR 테이블은 유사한 (중복) 상태가 함께 병합되어 개별 상태가 인코딩하는 컨텍스트 / 예측 정보를 효과적으로 폐기하기 때문에 더 작습니다. 장점은 동일한 문법에 대해 훨씬 작은 구문 분석 테이블을 얻을 수 있다는 것입니다.

단점은 모든 LR 문법이 LALR 테이블로 인코딩 될 수 없다는 것입니다. 더 복잡한 문법은 더 복잡한 예견을 가지므로 단일 병합 상태 대신 두 개 이상의 상태가 발생하기 때문입니다.

주요 차이점은 LR 테이블을 생성하는 알고리즘이 상태에서 상태로의 전환 사이에 더 많은 정보를 전달하는 반면 LALR 알고리즘은 그렇지 않다는 것입니다. 따라서 LALR 알고리즘은 주어진 병합 상태가 실제로 둘 이상의 개별 상태로 남아 있어야하는지 여부를 알 수 없습니다.

---

또 다른 답변 (YAA).

SLR (1), LALR (1) 및 LR (1)에 대한 파싱 알고리즘은 Ira Baxter가 말한 것과 동일
하지만 파서 생성 알고리즘으로 인해 파서 테이블이 다를 수 있습니다.

SLR 파서 생성기는 LR (0) 상태 머신을 생성하고 문법 (FIRST 및 FOLLOW 집합)에서 미리보기를 계산합니다. 이것은 단순한 접근 방식이며 LR (0) 상태 시스템에 실제로 존재하지 않는 충돌을보고 할 수 있습니다.

LALR 파서 생성기는 LR (0) 상태 머신을 생성하고 LR (0) 상태 머신 (터미널 전환을 통해)에서 미리보기를 계산합니다. 이것은 올바른 접근 방식이지만 때때로 LR (1) 상태 시스템에 존재하지 않는 충돌을보고합니다.

Canonical LR 파서 생성기는 LR (1) 상태 시스템을 계산하고 미리보기는 이미 LR (1) 상태 시스템의 일부입니다. 이러한 파서 테이블은 매우 클 수 있습니다.

A Minimal LR parser generator computes an LR(1) state machine, but merges compatible states during the process, and then computes the look-aheads from the minimal LR(1) state machine. These parser tables are the same size or slightly larger than LALR parser tables, giving the best solution.

LRSTAR 10.0 can generate LALR(1), LR(1), CLR(1) or LR(*) parsers in C++, whatever is needed for your grammar. See this diagram which shows the difference among LR parsers.

[Full disclosure: LRSTAR is my product]

---

Suppose a parser without a lookahead is happily parsing strings for your grammar.

Using your given example it comes across a string dc, what does it do? Does it reduce it to S, because dc is a valid string produced by this grammar? OR maybe we were trying to parse bdc because even that is an acceptable string?

As humans we know the answer is simple, we just need to remember if we had just parsed b or not. But computers are stupid :)

Since an SLR(1) parser had the additional power over LR(0) to perform a lookahead, we know that any amounts of lookahead cannot tell us what to do in this case; instead, we need to look back in our past. Thus comes the canonical LR parser to the rescue. It remembers the past context.

The way it remembers this context is that it disciplines itself, that whenever it will encounter a b, it will start walking on a path towards reading bdc, as one possibility. So when it sees a d it knows whether it is already walking a path. Thus a CLR(1) parser can do things an SLR(1) parser cannot!

But now, since we had to define so many paths, the states of the machine gets very large!

So we merge same looking paths, but as expected it could give rise to problems of confusion. However, we are willing to take the risk at the cost of reducing the size.

This is your LALR(1) parser.

---

Now how to do it algorithmically.

When you draw the configuring sets for the above language, you will see a shift-reduce conflict in two states. To remove them you might want to consider an SLR(1), which takes decisions looking at a follow, but you would observe that it still won't be able to. Thus you would, draw the configuring sets again but this time with a restriction that whenever you calculate the closure, the additional productions being added must have strict follow(s). Refer any textbook on what should these follow be.

---

The basic difference between the parser tables generated with SLR vs LR, is that reduce actions are based on the Follows set for SLR tables. This can be overly restrictive, ultimately causing a shift-reduce conflict.

An LR parser, on the other hand, bases reduce decisions only on the set of terminals which can actually follow the non-terminal being reduced. This set of terminals is often a proper subset of the Follows set of such a non-terminal, and therefore has less chance of conflicting with shift actions.

LR parsers are more powerful for this reason. LR parsing tables can be extremely large, however.

An LALR parser starts with the idea of building an LR parsing table, but combines generated states in a way that results in significantly less table size. The downside is that a small chance of conflicts would be introduced for some grammars that an LR table would otherwise have avoided.

LALR parsers are slightly less powerful than LR parsers, but still more powerful than SLR parsers. YACC and other such parser generators tend to use LALR for this reason.

P.S. For brevity, SLR, LALR and LR above really mean SLR(1), LALR(1), and LR(1), so one token lookahead is implied.

---

SLR parsers recognize a proper subset of grammars recognizable by LALR(1) parsers, which in turn recognize a proper subset of grammars recognizable by LR(1) parsers.

Each of these is constructed as a state machine, with each state representing some set of the grammar's production rules (and position in each) as it's parsing the input.

The Dragon Book example of an LALR(1) grammar that is not SLR is this:

S → L = R | R
L → * R | id
R → L

Here is one of the states for this grammar:

S → L•= R
R → L•

The • indicates the position of the parser in each of the possible productions. It doesn't know which of the productions it's actually in until it reaches the end and tries to reduce.

Here, the parser could either shift an = or reduce R → L.

An SLR (aka LR(0)) parser would determine whether it could reduce by checking if the next input symbol is in the follow set of R (ie, the set of all terminals in the grammar that can follow R). Since = is also in this set, the SLR parser encounters a shift-reduce conflict.

However, an LALR(1) parser would use the set of all terminals that can follow this particular production of R, which is only $ (ie, end of input). Thus, no conflict.

As previous commenters have noted, LALR(1) parsers have the same number of states as SLR parsers. A lookahead propagation algorithm is used to tack lookaheads on to SLR state productions from corresponding LR(1) states. The resulting LALR(1) parser can introduce reduce-reduce conflicts not present in the LR(1) parser, but it cannot introduce shift-reduce conflicts.

In your example, the following LALR(1) state causes a shift-reduce conflict in an SLR implementation:

S → b d•a / $
A → d• / c

The symbol after / is the follow set for each production in the LALR(1) parser. In SLR, follow(A) includes a, which could also be shifted.

---

One simple answer is that all LR(1) grammars are LALR(1) grammars. Compared to LALR(1), LR(1) has more states in the associated finite-state machine (more than double the states). And that is the main reason LALR(1) grammars require more code to detect syntax errors than LR(1) grammars. And one more important thing to know regarding these two grammars is that in LR(1) grammars we might have less reduce/reduce conflicts. But in LALR(1) there is more possibility of reduce/reduce conflicts.

---

In addition to the answers above, this diagram demonstrates how different parsers relate:

참고URL : https://stackoverflow.com/questions/2676144/what-is-the-difference-between-lr-slr-and-lalr-parsers