LL 파서

컴퓨터 과학에서 LL 파서(왼쪽에서 오른쪽으로, 가장 왼쪽 파생)는 제한된 컨텍스트프리 언어를 위한 하향식 파서입니다.왼쪽에서 오른쪽으로 입력을 해석하여 문장의 왼쪽 끝에 파생됩니다.

LL 파서는 문장을 해석할 때 lookahead 토큰을 k개 사용하는 경우 LL(k) 파서라고 합니다.문법은 LL(k) 파서를 구성할 수 있는 경우 LL(k) 문법이라고 합니다.공식 언어는 LL(k) 문법이 있으면 LL(k) 언어라고 불립니다.LL(k) 언어 집합은 각 k 0 ^[1]0에 대해 LL(k+1) 언어의 집합으로 적절히 포함됩니다.결국 모든 컨텍스트가 없는 언어가 LL(k) 파서로 인식되는 것은 아닙니다.

LL 파서는 LL 정규 언어를 해석하는 경우 LL 정규(^{[clarification needed][2][3][4]}LLR)라고 불립니다.LLR 문법의 클래스는 k마다 모든 LL(k) 문법을 포함합니다.모든 LLR 문법에 대해 선형 ^{[citation needed]}시간으로 문법을 해석하는 LLR 파서가 존재합니다.

두 가지 명명 특이치 파서 유형은 LL(*)과 LL(무한)입니다.파서는 LL(*)/LL(finite) 해석 전략을 사용하는 경우 LL(*)/LL(finite)이라고 불립니다.^[5][6] LL(*) 및 LL(finite) 파서는 기능적으로 PEG 파서와 더 유사합니다.LL(finite) 파서는 임의의 LL(k) 문법을 예측 및 예측 비교의 양으로 최적으로 해석할 수 있습니다.LL(*) 전략으로 해석할 수 있는 문법의 클래스는 구문 술어와 의미 술어의 사용으로 인해 일부 문맥에 민감한 언어를 포함하지만 식별되지 않았습니다.LL(*) 파서는 TDPL ^[7]파서로 간주하는 것이 좋습니다.일반적인 오해와 달리 LL(*) 파서는 일반적으로 LLR이 아니며, 구조에 의해 평균 성능 저하(선형 시간에 대해 초선형) 및 최악의 경우 성능 저하(선형 시간에 대해 지수)가 보장됩니다.

LL 문법, 특히 LL(1) 문법은 매우 실용적입니다.이러한 문법의 파서는 구축이 용이하며, 많은 컴퓨터 언어가 이러한 ^[8]이유로 LL(1)이 되도록 설계되어 있기 때문입니다.LL 파서는 LR 파서와 유사한 테이블 기반 ^{[citation needed]}파서입니다.LL 문법은 재귀 강하 파서로 구문 분석할 수도 있습니다.웨이트와 구스에 따르면,^[9] LL(k) 문법은 스턴스와 루이스에 의해 도입되었다.^[10]

개요

주어진 문맥이 없는 문법에 대해 파서는 가장 왼쪽의 파생어를 찾으려고 합니다.$문법 G$의 예를 다음에 제시하겠습니다$.$

1. ${\displaystyle S\to E}$
2. ${\displaystyle E\to(E+E)}$
3. $(\displaystyle E\toi)$

w $=$( (${\displaystyle i}$ +${\displaystyle i}$) +${\displaystyle i}$ ) ${{displaystyle$ w$=(i+i$)+i$$$}$에 $대한{\displaystyle }$ 가장 왼쪽 파생은 다음과 같습니다.

${\displaystyle S\{(1)\rightarrow}}\E\{오버셋 {(2)}{\rightarrow}}\(E+E){\rightarrow}}\(((E+E)+E)\\{rightarrow}}\(오른쪽 화살표)$

일반적으로 가장 왼쪽에 있는 비단말기를 확장하는 규칙을 선택할 때 여러 가지 방법이 있습니다.위의 예의 스텝2에서는 파서는 규칙2 또는 규칙3 중 어느 쪽을 적용할지를 선택해야 합니다.

${\displaystyle S\{(1)}{\오른쪽 화살표}}\E\{{(?)}{\오른쪽 화살표}}}\?}$

효율적으로 하기 위해서는 파서는 가능한 한 백트래킹 없이 결정적으로 이 선택을 할 수 있어야 합니다.일부 문법의 경우 읽지 않은 입력(읽지 않고)을 훔쳐봄으로써 이를 수행할 수 있습니다.이 예에서는 파서가 다음 읽지 않은 기호가$$(\$displaystyle()$임을 알고 있는 경우 사용할 수 있는 올바른 규칙은 2뿐입니다.

${\displaystyle \mathrm{일반적}}$으로 L${\displaystyle L}$ (${\displaystyle }$k$$) \ $displaystyle$LL ($k$ )파서는$$ k$$\ $displaystyle$ k$$symbols$$ $at$를 앞쪽으로 볼 수 있습니다.단, 문법에 $따라서는{\displaystyle }$ L ($$k$$) \ $displaystyle$LL${\displaystyle }$($k$ )${\displaystyle \mathrm{파서}}$가 인식되는 k \ $displaystyle$ k$$}파서가 존재하는지 여부를 판별할 수 없습니다.$각{\displaystyle }$k(\$displaystyle$ k$)$에 대해 L$(k$)\$displaystyle LL($k) 파서에서는$$ $인식$할 수 없지만 ${\displaystyle L(\mathrm{k}}$+$$1)\$displaystyle$ LL$(k+1$에서는 인식할 수 없는 언어가 있습니다.

위의 분석을 사용하여 다음과 같은 정식 정의를 내릴 수 있습니다.

G$(\displaystyle$ G$)$를 문맥이 없는 문법, $k{\displaystyle }$ $1$1로 $합니다{\displaystyle }$.G$(\$$displaystyle$$$G$)$는 L$)$이라고 합니다.단, 가장 왼쪽의 2개의 파생물에 대해서만 L$(k$이라고 합니다.

1. $\ display style S \ \ \ rightarrow \ wA \ alpha \ \ Rightarrow \ \ \ cdots \ \ \ beta \ alpha \ \ \ Rightarrow \ cdots \ \ wu }$
2. $\displaystyle S\\rightarrow\wA\alpha\Rightarrow\\cdots\w\gamma\alpha\Rightarrow\cdots\rightarrow\wv}$

string$$u$${ $display style$ k$$$}$ $k$ k $the{\displaystyle }$ the the the {\ u { display style k$$} $the{\displaystyle }$ the ${\$v { $display style$ $v$$$}의$$$$ 프레픽스는 ${\displaystyle \text{β}}$ $displaystyle$ \$=$\ $display$ style $k$를 $의미$합니다.

이 정의에서 S$(\displaystyle$ S$)$는 시작 $기호$이고 A$(\displaystyle$ A$)$는 터미널 이외의 기호입니다.이미 $파생$된 $입력$ w\$displaystyle$ w$,$ 그러나$$ $읽지{\displaystyle }$ 않은$$u$\displaystyle$ u 및 $\displaystyle$v는$$ 터미널 문자열입니다.$그리스{\displaystyle }$ $문자{\displaystyle }$α(\$displaystyle \alpha$$$β(\$displaystyle \beta)$ 및$$$\beta {\displaystyle }$(\$displaystyle \gamma)$는 터미널과 비터미널의 모든 문자열을 나타냅니다(공백일 수 있음).프리픽스 길이는 룩어헤드버퍼 사이즈에 대응하고 정의상 이 버퍼는 다른 워드의 파생어 2개를 구별하기에 충분합니다.

파서

${\displaystyle L}$L (${\displaystyle k}$ )$${$display style$LL($k)}$ 파서는$$ 결정론적 푸시다운 오토마톤으로, $다음{\displaystyle }$k \$displaystyle$ k$}$ 입력$$ 기호를 읽지 않고 엿볼 수 있습니다.버퍼와 입력 알파벳 모두 크기가 유한하기 때문에 이 피크 기능은 룩어헤드 버퍼 내용을 유한 상태 공간에 저장함으로써 에뮬레이트할 수 있습니다.결과적으로, 이것은 자동화를 더 강력하게 만드는 것이 아니라, 편리한 추상화이다.

스택 알파벳은 ${\displaystyle \gamma }$ ${\displaystyle =}$ N ${\displaystyle \cup }$ ${\displaystyle \mathrm{\sigma display}}$（ \ $displaystyle$\$Gamma = N$ \$cup$ \ $Sigma$ 。여기서 다음과 같이 입력합니다.

• $(\displaystyle$ N$)$은 비터미널 집합입니다.
• $σ \$ $displaystyle$ \$$Sigma$$ }단말기(입력) 심볼 세트.특수 입력 종료(EOI$)$ $심볼$ $ \ \$$displaystyle \$$$ } 。

파서 스택에는 처음에 EOI 위에${\displaystyle \text{시작}}$ 기호${\displaystyle \mathrm{}}$[S$$]\displaystyle [\$S$\backslash \$]$가 포함되어 있습니다.동작 중에 파서는 스택 상단의 $기호{\displaystyle }$ X$(\displaystyle$ X$)$를 반복해서 바꿉니다.

• $X{\displaystyle }$ ${\displaystyle \in }$ {\$displaystyle$$$X$\in$ N$$}이고 규칙 ${\displaystyle X}$ $→$ α {\$displaystyle X$\to \alpha $\}$인 경우$α$ {\displaystyle X$\to$ \alpha$\}$를 사용합니다.
• $($ $표기법$에서는 \$displaystyle \lambda)$가 있는 경우$,$ 즉 $X{\displaystyle }$$(\displaystyle$ X$\in \Sigma$가 스택에서 팝업됩니다.이 경우 입력 $기호{\displaystyle }$x(\$displaystyle$ X$)$가 읽혀지고 X$(\style$ X$)$가 표시된다.

스택에서 마지막으로 삭제되는 기호가 EOI일 경우 해석은 성공합니다.자동은 빈 스택을 통해 수신합니다.

상태 및 전이 함수는 명시적으로 지정되어 있지 않습니다.대신 보다 편리한 해석 테이블을 사용하여 지정(생성)됩니다.이 테이블은 다음 매핑을 참조해당 매핑은 다음과 같습니다.

• 행: 스택 상단 $기호{\displaystyle }$ X$(\displaystyle$ X$)$
• 열: ${\displaystyle w}$\ $displaystyle$w \$leq$ k$$} 미리$$ 버퍼 내용 보기
• 셀: X ${\displaystyle \to }$$\alpha {\displaystyle }$ {\$displaystyle$ X$\to$ \$alpha}$ $또는$ ${\$ {\$displaystyle \ilon}$ 규칙 번호

파서가 유효한 천이를 실행할 수 없는 경우 입력은 거부됩니다(빈 셀).테이블을 보다 콤팩트하게 하기 위해 일반적으로 단말기가 아닌 행만 표시됩니다.이는 단말기의 조작이 동일하기 때문입니다.

구체적인 예

세우다

LL(1) 파서의 동작을 설명하기 위해 다음과 같은 작은 LL(1) 문법을 검토합니다.

1. S → F
2. S → ( S + F )
3. F → a

및 다음 입력을 해석합니다.

( a + a )

문법을 위한 LL(1) 해석 테이블은 비말단 각각에 대한 행과 각 단자(여기서 $로 표현되며 입력 스트림의 종료를 나타내기 위해 사용되는 특수 단자를 포함한다)에 대한 열을 가진다.

표의 각 셀은 최대 1개의 문법 규칙(숫자로 식별)을 가리킬 수 있습니다.예를 들어 위의 문법에 대한 해석표에서는 비단말기 'S' 및 단말기 '()'의 셀이 규칙 번호2를 가리키고 있습니다.

	(	)	a	+	$
S	2	—	1	—	—
F	—	—	3	—	—

구문 분석 테이블을 구성하는 알고리즘에 대해서는 이후 섹션에서 설명하지만 먼저 구문 분석기가 구문 분석 테이블을 사용하여 입력을 처리하는 방법에 대해 설명합니다.

해석 절차

각 단계에서 파서는 입력 스트림에서 다음으로 사용 가능한 심볼과 스택에서 최상위 심볼을 읽습니다.입력 기호와 스택톱 기호가 일치하는 경우 파서는 둘 다 폐기하고 입력 스트림과 스택에 일치하지 않는 기호만 남습니다.

따라서 파서는 첫 번째 단계에서 입력 기호 '()'와 스택 탑 기호 'S'를 읽습니다.구문 분석 테이블 명령은 입력 기호 '('로 시작하는 열과 스택 탑 기호 'S'로 시작하는 행에서 가져옵니다. 이 셀에는 규칙 (2)를 적용하도록 파서에 지시하는 '2'가 포함되어 있습니다.파서는 스택에서 'S'를 삭제하고 ')', 'F', '+', 'S', 'S'()를 눌러 스택에서 'S'를 'S'로 고쳐 써야 합니다.이것에 의해, 룰 번호 2가 출력에 써집니다.그 후 스택은 다음과 같이 됩니다.

[ ( , S , + , F , $ )

두 번째 단계에서 파서는 입력 스트림과 스택에서 '('를 삭제합니다.이는 일치하기 때문입니다.이것으로 스택은 다음과 같이 됩니다.

[ S , + , F , $ ]

이제 파서는 입력 스트림에 'a'가 있고 스택 상단으로 'S'가 있습니다.해석 테이블은 문법 규칙 (1)을 적용하여 규칙 번호1을 출력 스트림에 쓰도록 지시합니다.스택은 다음과 같습니다.

[ F , + , F , $ ]

이제 파서는 입력 스트림에 'a'가 있고 스택 상단으로 'F'가 있습니다.해석 테이블은 문법 규칙 (3)을 적용하여 규칙 번호3을 출력 스트림에 쓰도록 지시합니다.스택은 다음과 같습니다.

[a, +, F, $]

이제 파서는 입력 스트림에 'a'가 있고 스택 상단에 'a'가 있습니다.이들은 동일하기 때문에 입력 스트림에서 삭제되고 스택의 상부에서 팝됩니다.그런 다음 파서는 입력 스트림에 '+'가 있고 '+'는 스택의 맨 위에 있습니다. 즉, 'a'와 같이 스택에서 팝업되어 입력 스트림에서 제거됩니다.그 결과 다음과 같습니다.

[F, , $]

다음 3단계에서 파서는 스택의 'F'를 'a'로 대체하고 규칙 번호 3을 출력 스트림에 쓰고 스택과 입력 스트림 모두에서 'a'와 ''를 제거합니다.따라서 파서는 스택과 입력 스트림 모두에서 '