단순 우선 순위 구문 분석기

컴퓨터 과학에서 단순 우선 순위 분석기는 단순한 우선 순위 문법만으로 사용할 수 있는 문맥 없는 그래머용 상향 파서의 일종이다.

파서의 구현은 일반적인 바텀업 파서와 상당히 유사하다.스택은 가장 오른쪽 파생에서 온 보초적 형태의 실행 가능한 접두사를 저장하는 데 사용된다.기호 ⋖, ⋖, ⋗은 피벗을 식별하고, 언제 Shift를 해야 하는지 또는 언제 감소해야 하는지 알기 위해 사용된다.

실행

• Wirth-Weber 우선 순위 관계 표를 계산하십시오.
• 시작 마커 $만 있는 스택으로 시작하십시오.
• 먼저 구문 분석되는 문자열(입력)이 엔딩 마커 $로 종료됨.
• 그렇지 않은 경우(Stack은 $S, 입력은 $) (S = 문법의 초기 기호)
  • 표에서 Top(스택)과 NextToken(입력) 사이의 관계 검색
  • 관계가 ⋖인지 ⋖인지 ⋖인지
    • 이동:
    • 푸시(스택, 관계)
    • 푸시(Stack, NextToken(입력))
    • RemoveNextToken(입력)
  • 관계가 ⋗이면
    • 감소:
    • 검색프로덕션ToReduce(스택)
    • RemovePivot(스택)
    • 테이블에서 프로덕션에서 Non 터미널과 스택에서 첫 번째 기호 사이의 관계 검색(위에서 시작)
    • 푸시(스택, 관계)
    • 푸시(Stack, Non terminal)

SearchProductionToReduce(스택)

• 상단으로부터 가장 가까운 search의 스택에서 피벗을 검색하다.
• 피벗과 같은 오른쪽의 문법을 찾아보다.

예

언어 지정:

E --> E + T' T' T' --> T T --> T * F F F -- > ( E') 숫자 E' --> E

num은 단자이고, lexer는 정수를 num으로 구문 분석한다.

및 구문 분석 표:

	E	이'	T	T'	F	+	*	(	)	숫자	$
E						⋖			⋗		⋗
이'									⋖
T						⋗	⋖		⋗		⋗
T'						⋗			⋗		⋗
F						⋗	⋗		⋗		⋗
+			⋖	⋖	⋖			⋖		⋖
*					⋖			⋖		⋖
(	⋖	⋖	⋖	⋖	⋖			⋖		⋖
)						⋗	⋗		⋗		⋗
숫자						⋗	⋗		⋗		⋗
$	⋖		⋖	⋖	⋖			⋖		⋖

STACK PRECEDENCE 입력 ACTION달러를<>2*(1+3)$ 시프트 드레스달러 <2>네(1+3)$ REDUCE(F->, num)달러를<>F>네(1+3)$(T->, F)달러를<>REDUCE, T=*(1+3)$ SHI.FT달러<T=me<>(1+3)$ 시프트 드레스달러<, T=*<>(<>1+3)$ 시프트 드레스달러<, T=*<>(<1>+3)$ REDUCE 4번(F->, num)(T->, F)(T자형 ->&T)(E->, T자형)달러<T=*<>(<>E-+3)$ 시프트 드레스달러<, T=*<>(<>E-+&l.T, 3)달러&lt달러 SHIFT, T=*<>(<>.E-+<3>)달러 REDUCE 3번(F->, num)(T->, F)(T자형 ->&T)달러<T=*<>(<>E-+)T>)$ 2번 REDUCE(E의 ->, E)달러를<>(E->, E+T), T=*<>(<>E의))$ 시프트 드레스달러<, T=*<>()E'))>달러 REDUC.E(F->.(E'))달러<T=*)F.$ REVENT (T -> T * F) $ T > $ REVENT 2회 (T' -> T)(E -> T') $ E > $ Aception

참조

• 알프레드 5세아호, 제프리 D.울먼(1977년).컴파일러 설계의 원리.제1판.애디슨-웨슬리
• 윌리엄 A.배럿, 존 D카우치(1979년).컴파일러 구조: 이론과 실천.과학 연구 협회
• 장폴 트런블레이, P. G. 소렌손(1985)컴파일러 글쓰기의 이론과 실천.맥그로-힐