LL 문법

C 문법은^[1] LL(1)이 아니다.아래 부분은 토큰을 소화한 파서를 보여준다.int v ;main(){"는 비단어를 도출하기 위한 규칙을 선택하는 것이다.Stmt". 첫 번째 룩어헤드 토큰만 보면 "v", 그것은 두 가지 대안 중 어느 것을 위한 것인지 결정할 수 없다.Stmt" 두 입력 연속이 가능하기 때문에 선택한다.두 번째 룩어헤드 토큰(노란색 배경)을 훔쳐봄으로써 차별을 받을 수 있다.

형식 언어 이론에서 LL 문법은 LL 파서가 파싱할 수 있는 문법으로서, 왼쪽에서 오른쪽으로 입력을 파싱하고 문장의 최좌측 파생(hence LL, 가장 오른쪽 파생을 구성하는 LR 파서 대비)을 구성한다.LL 문법이 있는 언어는 LL 언어로 알려져 있다.이러한 형식은 각각 결정론적 상황 없는 언어(DCFG)와 결정론적 상황 없는 언어(DCFL)의 하위 집합을 형성한다.어떤 사람은 주어진 문법이나 언어가 "LL 문법/언어"이거나 단순히 "LL"이라고 말하여 그것이 이 반에 있다는 것을 나타낸다.

LL 파서는 LR 파서와 유사한 테이블 기반 파서다.LL 그래머는 역추적 없이 재귀적 하강 파서인 예측 파서(repursive down parser)에 의해 구문 분석할 수 있는 정확하고 손으로 쉽게 작성할 수 있다.이 글은 LL 그래머의 공식 특성에 관한 것이다. 파싱은 LL 파서 또는 재귀 하강 파서를 참조하십시오.

형식 정의

유한 케이스

자연수 $k\geq 0$ $k\geq 0$ $k\geq 0$ ${\displaystyle k\geq$ 0 $}$ 을(를) 지정하면 $k\geq 0$ 문맥 없는 $G=(V,\Sigma ,R,S)$ G $G=(V,\Sigma ,R,S)$ = $G=(V,\Sigma ,R,S)$ , $G=(V,\Sigma ,R,S)$ , $G=(V,\Sigma ,R,S)$ , $G=(V,\Sigma ,R,S)$ ) ${\displaystyle$ G $=(V,\Sigma ,R,S)}$ 은 LL(k) 문법이다 $G=(V,\Sigma ,R,S)$ .

$w\in \Sigma ^{*}$ ∈ ∗ $w\in \Sigma ^{*}$ $\$ {\ $displaystyle$ $w\$ in\ $Sigma$ $w\in \Sigma ^{*}$ $^{*}}$ $k$ 의 $w\in \Sigma ^{*}$ $k$ 각 $w\in \Sigma ^{*}$ 기호 문자열에 대해,
각 비터미널 기호 $A\in V$ 에 대해 V $A\in V$ 및
\ $Sigma ^{*}$ 인 각 터미널 기호 문자열이 $w_{1}\in \Sigma ^{*}$ } $w_{1}\in \Sigma ^{*}$ ${\$ in \Sigma ^{*}}인 경우 $w_{1}\in \Sigma ^{*}$

\ $Sigma$ ^{*}에 일부 터미널 기호 문자열 $w_{2},w_{3}\in \Sigma ^{*}$ $w_{2},w_{3}\in \Sigma ^{*}$ , w $w_{2},w_{3}\in \Sigma ^{*}$ $w_{2},w_{3}\in \Sigma ^{*}$ ∗ $w_{2},w_{3}\in \Sigma ^{*}$ $\$ {\ $displaystyle w_{2$ }, $w_{3}\$ $in$ \Sigma $w_{2},w_{3}\in \Sigma ^{*}$ ^{*}}}에 대해 $r\in R$ 최대 $r\in R$ 의 생산 규칙 r ${\displaystyle$ r $\{\}$ 이 있다 $w_{2},w_{3}\in \Sigma ^{*}$

$w_{1}Aw_{3}$ $w_{1}Aw_{3}$ $w_{1}Aw_{3}$ w $w_{1}Aw_{3}$ ${\$ . $}}Aw_{3}}$ 은(는) 시작 $기호$ S $S$ 에서 파생될 수 있으며 $w_{1}Aw_{3}$ $S$
$w_{2}$ $w_{2}$ ${\$ }}: 규칙 $r$ $r$ 을(를) 처음 적용한 후 $A$ $A$ $A$ 에서 파생될 수 있으며 $w_{2}$ $r$
$w$ $w$ 및 $w$ $w_{2}w_{3}$ $w_{2}w_{3}$ w $w_{2}w_{3}$ ${\$ 의 첫 $번째$ k $k$ 기호가 $k$ 일치한다 $w_{2}w_{3}$ .^[2]

대안이지만 동등한 형식 정의는 $G=(V,\Sigma ,R,S)$ 과 같다: G $G=(V,\Sigma ,R,S)$ = $G=(V,\Sigma ,R,S)$ ( $G=(V,\Sigma ,R,S)$ , $G=(V,\Sigma ,R,S)$ , $G=(V,\Sigma ,R,S)$ , R $G=(V,\Sigma ,R,S)$ , $G=(V,\Sigma ,R,S)$ ) ${\displaystyle$ G $=(V,\Sigma ,R,S)}$ 는 임의의 $G=(V,\Sigma ,R,S)$ 파생에 대한 LL(k) 문법이다.

${\begin{array}{cccccc}S&\Rightarrow ^{L}&w_{1}A\chi &\Rightarrow &w_{1}\nu \chi &\\Rightarrow ^{*&w_{1}w_{1}w_{2}w_{3}\S&\Rightarrow ^{L}&w_{1}A\chi &\Rightarrow &w_{1}\오메가 \chi &\\Rightarrow ^{*w_{1}w'_{2}w'_{3}\\end{array}}}}}}$

$w_{2}w_{3}$ $w_{2}w_{3}$ $w_{2}w_{3}$ $w_{2}w_{3}$ ${\$ 의 첫 $번째$ k ${\$ $displaystyle w_{2}w'_{3}$ 기호가 $k$ w $w'_{2}w'_{3}$ $w'_{2}w'_{3}$ w $w'_{2}w'_{3}$ w의 기호와 일치할 $w_{2}w_{3}$ 때, $w'_{2}w'_{3}$ $\nu =\omega$ = $\nu =\omega$ = ${\displaystyle \nu =\omega$ $\nu =\omega$ ^[3]^[4]

비공식적으로 파서가 w $w_{1}Aw_{3}$ $w_{1}Aw_{3}$ $w_{1}Aw_{3}$ w $w_{1}Aw_{3}$ ${\$ 을 파생한 경우 $}}Aw_{$ $3$ $w_{1}Aw_{3}$ 을(를 $)$ 사용하여 파서는 $A$ 입력에서 이미 $w_{1}$ 소비된 가장 왼쪽의 비터미널 및 $w_{1}$ $w_{1}$ ${\$ $w_$ ${1$ }}을(를) 확인한 다음, $w_{1}$ ${\$ k} $기호와$ 현재 입력에서 $w$ $다음$ k{\ $displaystyle$ $k$ $} 기호$ 를 $k$ 훔쳐봄으로써 인증서와 함께 식별할 수 있다.a. $A$ $A$ 에 $r$ 대한 프로덕션 $규칙$ r ${\displaystyle r$ $A$

과거 입력 $w_{1}$ $w_{1}$ ${\$ 1}를 고려하지 않아도 규칙 식별이 가능할 때 문법은 강한 LL(k) 문법이라고 한다 $w_{1}$ ^[5]강한 LL(k) 문법의 공식적 정의에서 $w_{1}$ $w_{1}$ ${\$ }의 범용 정량자가 생략되고 $w_{1}$ $w_{1}$ w $w_{2},w_{3}$ ${\$ ${2}, w_{$ 의 "일부" 정량자에 w $w_{2},w_{3}$ ${\$ w_{3}. 모든 LL(k) 문법에 대해 구조적으로 동등한 LL(k) 문법이 될 수 있다.구성의^[6]

LL(k) 언어의 클래스는 엄격하게 증가하는 집합의 순서를 형성한다: LL(0) ⊊ LL(1) ⊊ LL(2) ⊊ ….^[7] 주어진 문법 G가 LL(k)인지 여부는 결정 가능하지만, 임의의 문법이 일부 k의 경우 LL(k)인지 여부는 결정 가능하지 않다.주어진 LR(k) 문법도 일부 m에 대한 LL(m) 문법일 경우 변경할 수 없다.^[8]

모든 LL(k) 문법도 LR(k) 문법이다.ε프리 LL(1) 문법도 SLR(1) 문법이다.빈 파생어와 비어 있지 않은 파생어가 모두 있는 기호를 가진 LL(1) 문법도 LALR(1) 문법이다.빈 파생만 있는 기호를 가진 LL(1) 문법은 LALR(1)일 수도 있고 아닐 수도 있다.^[9]

LL 그래머는 왼쪽 재귀가 포함된 규칙을 가질 수 없다.^[10]ε프리인 각 LL(k) 문법은 Greibach 정상형(definitional recursion이 있는 규칙이 없는 정의)에서 동등한 LL(k) 문법으로 변형될 수 있다.^[11]

일반 케이스

$\Sigma$ $\Sigma$ 을(를) 단자 문자로 설정하십시오 $\Sigma$ . $R\in \pi$ $\Sigma ^{*}$ $∈$ {\ $displaystyle \Sigma$ ^{*}의 파티션 $\pi$ $\$ {\ $displaystyle$ $R$ \ $in \pi}$ 이 $R\in \pi$ (가) 언어 $R$ $R$ 이(가) 정규 $R$ 파티션이라고 한다 $\Sigma ^{*}$ .

Let $G=(V,\Sigma ,R,S)$ be a context free grammar and let $\pi =\{R_{1},\dotso ,R_{n}\}$ be a regular partition of $\Sigma ^{*}$ . We say that $G$ is an LL( $\pi$ ) grammar if, f또는 임의의 파생

${\begin{array}{cccccc}S&\Rightarrow ^{L}&w_{1}A\chi _{1}&\Rightarrow &w_{1}\nu \chi \chi _{1}&\Rightarrow ^{*&w_{1}x\\\S&\오른쪽 화살표 ^{L}&w_{2}A\chi _{2}&\Rightarrow &w_{2}\오메가 \chi _{2}&\Rightarrow ^{*w_{2}y,\\end{array}}}}}}$

그러한 $x\equiv y\mod \pi$ $x\equiv y\mod \pi$ $x\equiv y\mod \pi$ $x\equiv y\mod \pi$ $x\equiv y\mod \pi$ $x\equiv y\mod \pi$ 뒤에 $x\equiv y\mod \pi$ $\nu =\omega$ = $\nu =\omega$ $\nu =\omega$ 이(가) 나타난다 $\nu =\omega$ ^[12]

문법 G는 LL $({\displaystyle$ $\Sigma ^*})$ 과 같이 $\Sigma ^{*}$ ${\$ displaystyle $\pi }}$ 의 정규 파티션이 있으면 LL-정규어(LLR)라고 한다.언어는 LL정규어법에 의해 생성되면 LL정규어다.

LLR 문법은 모호하지 않고 좌회귀할 수 없다.

모든 LL(k) 문법은 LLR이다.모든 LL(k) 문법은 결정론적이지만, 결정론적이지 않은 LLR 문법이 존재한다.^[13]따라서 LLR 그래머의 등급은 각 k에 대한 LL(k)의 조합보다 확실히 크다.

정규 파티션 $\pi$ {\ $displaystyle \pi$ 을(를) 지정하면 주어진 문법이 $({\displaystyle \pi$ }) $\pi$ 인지 여부를 결정할 수 있다.그러나 임의의 문법 G가 LLR인지 여부는 결정되지 않는다.문법 G가 G를 위한 정규 칸막이를 찾는 데 필요한 정규 언어를 생성하는지 여부를 결정하는 것이 포스트 통신문제로 전락할 수 있기 때문이다.

모든 LLR 문법은 LR-정규어(LRR, LR(k) 문법에 상응하는^[clarify] 것)이지만 LR(1) 문법은 LLR이 아닌 것이 존재한다.^[13]

역사적으로 LLR 그래머는 LRR 그래머의 발명을 따랐다.일반 칸막이가 주어지면, 무어 기계는 정규 생산의 예를 확인하면서 오른쪽에서 왼쪽으로 파싱을 변환하도록 제작될 수 있다.일단 그렇게 되면, LL(1) 파서는 변환된 입력을 선형 시간 내에 처리하기에 충분하다.따라서 LLR 파서는 동등하게 효율적이면서도 LL(k) 파서보다 엄격히 큰 그래머의 종류를 처리할 수 있다.그럼에도 불구하고 LLR의 이론은 큰 응용이 없다.한 가지 가능성 있고 매우 그럴듯한 이유는 LL(k)과 LR(k) 파서를 위한 생성 알고리즘이 있지만, LLR/LRR 파서를 생성하는 문제는 일반 파티션을 미리 구성하지 않는 한 이해할 수 없는 문제가 되기 때문이다.그러나 문법이 주어진 적절한 정규 칸막이를 구축하는 문제조차도 이해할 수 없다.

단순 결정론적 언어

문맥이 없는 문법은 단순한 결정론적,^[14] 또는 단지 단순한 문법이라고 불린다.^[15]

Greibach 정규 형식( $Z\rightarrow aY_{1}\ldots Y_{n},n\geq 0$ 즉, 각 규칙에는 $Z\rightarrow aY_{1}\ldots Y_{n},n\geq 0$ → $Z\rightarrow aY_{1}\ldots Y_{n},n\geq 0$ 1 … $Z\rightarrow aY_{1}\ldots Y_{n},n\geq 0$ $Z\rightarrow aY_{1}\ldots Y_{n},n\geq 0$ $Z\rightarrow aY_{1}\ldots Y_{n},n\geq 0$ 0 $Z\rightarrow aY_{1}\ldots Y_{n},n\geq 0$ {\ $displaystyle Z\rightarrow aY_{1}\ldots Y_{n},n\geq$ 0 $})$ 및
동일한 비터미널 $Z$ $Z$ 에 대한 다른 오른쪽 측면은 항상 $Z$ $다른$ 단자 a ${\displaystyle$ a $}$ 로 시작한다 $a$

문자열의 집합은 단순한 결정론적, 또는 단순한 결정론적 문법을 가진 언어라고 불린다.

Greibach 정상 형태의 grammar-free LL(1) 문법을 가진 언어의 클래스는 단순한 결정론적 언어의 클래스와 같다.^[16]이 언어 클래스는 ε을 포함하지 않는 정규 세트를 포함한다.^[15]등가성은 그것에 대해 결정 가능한 반면, 포함은 그렇지 않다.^[14]

적용들

LL grammar, 특히 LL(1) grammar는 LL 파서나 재귀 강하 파서 등으로 구문 분석하기 쉽고, 많은 컴퓨터 언어가^[clarify] 이러한 이유로 LL(1)로 설계되어 있어 실용적 관심이 크다.K 값이 높은 문법 기반 언어는 전통적으로 구문 분석하기 어려운 것으로 간주되어^{[citation needed]} 왔으나, 임의의 k에 대해 LL(k) 문법을 지원하는 파서 발생기의 가용성과 광범위한 사용을^{[citation needed]} 감안할 때 현재는 그렇지 않다.

참고 항목

LL(k) 및 LL(*) 파서 리스트의 파서 생성기 비교

메모들

^ Kernighan & Ritchie 1988, 부록 A.13 "Grammar", 페이지 193 ff.상단 이미지 부분은 EBNF와 유사한 표기법으로 단순하게 발췌한 것을 보여준다.
^ 로젠크란츠 & 스턴스(1970, 페이지 227).Def.1. 저자들은 그 사례를 k=0으로 보지 않는다.
^ where " $\Rightarrow ^{L}$ " denotes derivability by leftmost derivations, and $w_{1},w_{2},w_{3},w'_{2},w'_{3}\in \Sigma ^{*}$ , $A\in V$ , and ${\displaystyle \chi ,\nu ,\omega$ $\in (\Sigma \cup V)^{*}}$
^ 와이트 앤 구스(1984, 페이지 123) 데프 5.22
^ 로젠크란츠 & 스턴스(1970, 페이지 235) 데프.2
^ 로젠크란츠 & 스턴스(1970, 페이지 235) 정리 2
^ Rosenkrantz & Stearns(1970, 페이지 246–247): " + ${\displaystyle$ $+$ 을 사용하여 "or"를 나타냄으로써 문자열 집합 $\{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}$ { $\{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}$ + $\{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}$ + $\{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}$ ) $\{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}$ : $\{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}$ ≥ $\{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}$ ${\displaystyle \{a^{n}(b^{k}d+b+b)$ $^{n:n\geq 1\}$ 에는 $LL(k+1)$ ( $LL(k+1)$ + $LL(k+1)$ 1 $LL(k+1)$ ) ${\displaystyle LL$ $k$ $+1)}$ 이(가) 있지만 $\{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}$ $,$ 각 k $k\geq 1$ ${\displaystyle k\geq$ 1 $}$ 에 $대해$ for-free LL ( $LL(k)$ 문법은 $LL(k)$ 없다 $k\geq 1$
^ 로젠크란츠 & 스턴스(1970, 페이지 254–255)
^ 비티(1982)
^ 로젠크란츠 & 스턴스(1970, 페이지 241) 레마 5
^ 로젠크란츠 & 스턴스(1970, 페이지 242) 정리 4
^ Poplawski, David (1977). "Properties of LL-Regular Languages". Purdue University. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
^ ^a ^b David A. Poplawski (Aug 1977). Properties of LL-Regular Languages (Technical Report). Purdue University, Department of Computer Science.
^ ^a ^b 코렌작&홉크로프트(1966)
^ ^a ^b 홉크로프트&울먼(1979년, 페이지 229년) 연습 9.3
^ 로젠크란츠 & 스턴스(1970, 페이지 243)

원천

Beatty, J. C. (1982). "On the relationship between LL(1) and LR(1) grammars" (PDF). Journal of the ACM. 29 (4 (Oct)): 1007–1022. doi:10.1145/322344.322350. S2CID 14700480.
Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 978-0-201-02988-8.
Kernighan, Brian W.; Ritchie, Dennis M. (April 1988). The C Programming Language. Prentice Hall Software Series (2nd ed.). Englewood Cliffs/NJ: Prentice Hall. ISBN 978-013110362-7.
Korenjak, A.J.; Hopcroft, J.E. (1966). "Simple deterministic languages". IEEE Conf. Rec. 7th Ann. Symp. on Switching and Automata Theory (SWAT). IEEE Pub. No. Vol. 16-C-40. pp. 36–46. doi:10.1109/SWAT.1966.22.
Parr, T.; Fisher, K. (2011). "LL(*): The Foundation of the ANTLR Parser Generator" (PDF). ACM SIGPLAN Notices. 46 (6): 425–436. doi:10.1145/1993316.1993548.
Rosenkrantz, D. J.; Stearns, R. E. (1970). "Properties of Deterministic Top Down Grammars". Information and Control. 17 (3): 226–256. doi:10.1016/s0019-9958(70)90446-8.
Waite, William M.; Goos, Gerhard (1984). Compiler Construction. Texts and Monographs in Computer Science. Heidelberg: Springer. ISBN 978-3-540-90821-0.

추가 읽기

Sippu, Seppo; Soisalon-Soininen, Eljas (1990). Parsing Theory: LR(k) and LL(k) Parsing. Springer Science & Business Media. ISBN 978-3-540-51732-0.

[FOOTNOTEKernighanRitchie1988Appendix_A.13_"Grammar",_p.193_ff._The_top_image_part_shows_a_simplified_excerpt_in_an_[[EBNF]]-like_notation.-1] Kernighan & Ritchie 1988, 부록 A.13 "Grammar", 페이지 193 ff.상단 이미지 부분은 EBNF와 유사한 표기법으로 단순하게 발췌한 것을 보여준다.

[2] 로젠크란츠 & 스턴스(1970, 페이지 227).Def.1. 저자들은 그 사례를 k=0으로 보지 않는다.

[3] where " $\Rightarrow ^{L}$ " denotes derivability by leftmost derivations, and $w_{1},w_{2},w_{3},w'_{2},w'_{3}\in \Sigma ^{*}$ , $A\in V$ , and ${\displaystyle \chi ,\nu ,\omega$ $\in (\Sigma \cup V)^{*}}$

[4] 와이트 앤 구스(1984, 페이지 123) 데프 5.22

[5] 로젠크란츠 & 스턴스(1970, 페이지 235) 데프.2

[6] 로젠크란츠 & 스턴스(1970, 페이지 235) 정리 2

[7] Rosenkrantz & Stearns(1970, 페이지 246–247): " + ${\displaystyle$ $+$ 을 사용하여 "or"를 나타냄으로써 문자열 집합 $\{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}$ { $\{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}$ + $\{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}$ + $\{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}$ ) $\{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}$ : $\{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}$ ≥ $\{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}$ ${\displaystyle \{a^{n}(b^{k}d+b+b)$ $^{n:n\geq 1\}$ 에는 $LL(k+1)$ ( $LL(k+1)$ + $LL(k+1)$ 1 $LL(k+1)$ ) ${\displaystyle LL$ $k$ $+1)}$ 이(가) 있지만 $\{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}$ $,$ 각 k $k\geq 1$ ${\displaystyle k\geq$ 1 $}$ 에 $대해$ for-free LL ( $LL(k)$ 문법은 $LL(k)$ 없다 $k\geq 1$

[8] 로젠크란츠 & 스턴스(1970, 페이지 254–255)

[9] 비티(1982)

[10] 로젠크란츠 & 스턴스(1970, 페이지 241) 레마 5

[11] 로젠크란츠 & 스턴스(1970, 페이지 242) 정리 4

[12] Poplawski, David (1977). "Properties of LL-Regular Languages". Purdue University. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)

[David_A._Poplawski-13] David A. Poplawski (Aug 1977). Properties of LL-Regular Languages (Technical Report). Purdue University, Department of Computer Science.

[Korenjak.Hopcroft.1966-14] 코렌작&홉크로프트(1966)

[Hopcroft.Ullman.1979.Exc.9.3-15] 홉크로프트&울먼(1979년, 페이지 229년) 연습 9.3

[16] 로젠크란츠 & 스턴스(1970, 페이지 243)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

Search