: 그것은 LR 수 있도록LR (1)이되도록 문맥 자유 문법을 어떻게 다시 작성합니까? 주어진 문맥 자유 문법에 대한
S -> G $
G -> PG | P
P -> id : R
R -> id R | epsilon
가 어떻게 문법을 다시합니까 (1)?
"id : .id"입력을 구문 분석 할 때 현재 문법에 shift/reduce 충돌이 있습니다. 여기서 "." 파서에 대한 입력 포인터입니다.
이 문법은 정규 표현식 (id : (id) *) +
을 만족하는 언어를 만듭니다. 동일한 언어에 대해 LR (1) 문법을 작성하기는 쉽습니다. 트릭은 유사한 구문 분석 트리가 있거나 적어도 원래 구문 분석 트리를 쉽게 복구 할 수있는 구문을 찾는 것입니다.
다음은 수동으로 생성 된 문법입니다.이 알고리즘은 일반적인 알고리즘과 약간 비슷합니다.
(id:id*)+행 : 문법을 유도
id(:id+)*:id*:
S → id G $
G → P G | P'
P' → : R'
P → : R
R' → ε | id R'
R → ε | id R
LALR (1) 사실상, 우리는 정규식을 재 작성.
실제로 모든 제작물을 오른쪽으로 하나의 토큰으로 이동 시켰으며 k≥1에 대해 LR(k+1) 문법의 LR(1) 문법을 만드는 데 사용할 수있는 일반적인 알고리즘이 있습니다. (I가 사용하고,이 알고리즘의 버전 S. Sippu & E. Soisalon-Soininen 권 II, 6.7 절에서 파싱 이론에서 온다.) 새로운 문법
비 단자 모양을 갖 V가 일본어 문법에서 기호 (a 말단 또는 비 - 말단 중 하나)과 x 및 y이다 (x, V, y) 최대 길이 말단 서열이다 k되도록 : y의
y ∈ FOLLOWk(V)
x ∈ FIRSTk(Vy)
(길이들 결과적 x 위력입력 끝이 후속 세트에 포함되는 경우 k보다 작아야합니다. 어떤 사람들은 k 끝 기호를 추가하여이 문제를 방지,하지만 난이 버전 그냥 간단하게 생각합니다.)
비 터미널 (x, V, y) 원래 문법에서 Vy에서 파생 된 문자열의 x -derivative를 생성합니다. 비공식적으로 문법 전체가 k 토큰으로 오른쪽으로 이동합니다. 각 비 터미널은 첫 번째 k 토큰이 누락 된 문자열과 일치하지만 다음 k 토큰으로 증가됩니다.
제작물은 원본 작품에서 기계적으로 생성됩니다. 첫째, 우리는 생산과, S'을 새로운 시작 심볼을 추가
S' → x (x, S, ε)
을 모든 x ∈ FIRSTk(S) 위해.명백한 동형가 있으므로
(x0,T,xm+1) → (x0,V0,x1) (x1,V1,x2) … (xm,Vm,xm+1)모든 단말 A위한
(Ax,A,xB) → B if |x| = k
(Ax,A,x) → ε if |x| ≤ k
들의 세트를 생성 : 다음, 모든 생산
T → V0 V1 … Vm우리는 제작의 세트를 생성 새로운 문법의 프로덕션에서부터 오래된 문법의 프로덕션에 이르기까지, 원래의 구문 분석 트리를 직접 작성할 수 있습니다.하지만 sema로 몇 가지 트릭을해야합니다. 구문 분석 트리에 올바르게 첨부하기 위해 ntic 값을 사용합니다.