구문 술어

구문 술어는 형식 문법에 있어서의 생산의 적용의 구문 유효성을 지정하고, 생산의 적용의 의미 유효성을 지정하는 의미 술어와 유사하다.이는 임의의 예측 기능을 제공함으로써 LL 파서의 인식 강도를 획기적으로 향상시키는 간단하고 효과적인 수단입니다.원래 구현에서 구문 서술어는 (α?)의 형태를 가지고 있었으며, 생산의 왼쪽 가장자리에만 나타날 수 있었다.필요한 구문 조건α는 문맥이 없는 유효한 문법 단편일 수 있습니다.

좀 더 형식적으로, 구문 술어는 생산 교점의 한 형태로 파서 사양 또는 형식 문법에서 사용됩니다.이러한 의미에서 술어라는 용어는 수학적 지시 함수의 의미를 갖는다.p와_2, p가 생산 규칙인 경우₁ p와₂ p가 모두 생성하는₁ 언어는 이들의 집합 교집합입니다.

일반적으로 정의 또는 구현되는 것처럼 구문 술어는 암묵적으로 프로덕션의 순서를 지정하여 이전에 지정된 사전 프로덕션의 우선순위가 동일한 결정 내에서 나중에 지정된 사전 프로덕션보다 높아지도록 합니다.프로그래머는 단순히 어떤 프로덕션과 일치해야 하는지 지정할 수 있기 때문에 모호한 프로덕션의 명확성을 제거할 수 있습니다.

Bryan Ford가 고안한 PEG(표현식 문법)의 해석은, 「술어가 아니다」를 허가해, 생산내의 어느 장소에나 술어를 표시할 수 있도록 하는 것으로, 이러한 간단한 술어를 확장합니다.또한 Ford는 메모화를 사용하여 힙 공간을 희생하면서 선형 시간 내에 이러한 문법을 처리하는 packrat 파싱을 발명했습니다.

PEG에 의해 허용된 술어의 선형 시간 해석을 지원할 수 있지만, 사전 예측의 보다 효율적인 구현으로 충분한 역추적을 피함으로써 메모화와 관련된 메모리 비용을 절감할 수 있습니다.이 접근방식은 ANTLR 버전3에 의해 구현되며, ANTLR 버전3에서는 예측에 결정론적 유한 오토마타를 사용합니다.이는 DFA의 전환("pred-LL(*")^[1] 중 하나를 선택하기 위해 술어 테스트가 필요할 수 있습니다.

개요

용어.

구문 술어라는 용어는 Parr & Quong에 의해 만들어졌으며, 이 형식의 술어를 의미 술어와 구별한다(또한 ^[2]논의된다).

구문 술어는 여러 문헌에서 다단계 매칭, 구문 분석 제약, 단순 술어라고 불립니다.(아래의 「참고 자료」섹션을 참조해 주세요).이 문서에서는 일관성을 유지하고 의미 술어와 구별하기 위해 구문 술어 전체를 사용합니다.

정식 마감 속성

Bar-Hilel 등은 ^[3]두 정규 언어의 교집합 또한 정규 언어이며, 즉 정규 언어는 교집합 아래에서 폐쇄된다는 것을 보여준다.

정규 언어와 문맥이 없는 언어의 교차점도 폐쇄되어 있으며, 적어도 Hartmanis 이후부터^[4] 문맥이 없는 두 언어의 교차점이 반드시 문맥이 없는 언어는 아니라는 것이 알려져 왔다(따라서 폐쇄되어 있지 않다).이는 표준 타입 1 언어인 $L=\{a^{n}b^{n}c^{n}:n\geq 1\}$ $=$ { $L=\{a^{n}b^{n}c^{n}:n\geq 1\}$ $L=\{a^{n}b^{n}c^{n}:n\geq 1\}$ n $L=\{a^{n}b^{n}c^{n}:n\geq 1\}$ : n $L=\{a^{n}b^{n}c^{n}:n\geq 1\}$ 1 $L=\{a^{n}b^{n}c^{n}:n\geq 1\}$ display 1 $L=\{a^{n}b^{n}c^{n}:n\geq 1\}$ } { $displaystyle$ L=\{ $a^{n}b^{n}c^{n$ }: $n\geq$ 1 $L=\{a^{n}b^{n}c^{n}:n\geq 1\}$ 을 사용하여 쉽게 입증할 수 있습니다.

 $L_{1}=\{a^{m}b^{n}c^{n}:m,n\geq 1\}$  1  $L_{1}=\{a^{m}b^{n}c^{n}:m,n\geq 1\}$  {  $L_{1}=\{a^{m}b^{n}c^{n}:m,n\geq 1\}$   $L_{1}=\{a^{m}b^{n}c^{n}:m,n\geq 1\}$   $L_{1}=\{a^{m}b^{n}c^{n}:m,n\geq 1\}$   $L_{1}=\{a^{m}b^{n}c^{n}:m,n\geq 1\}$   $L_{1}=\{a^{m}b^{n}c^{n}:m,n\geq 1\}$  n $L_{1}=\{a^{m}b^{n}c^{n}:m,n\geq 1\}$ : $L_{1}=\{a^{m}b^{n}c^{n}:m,n\geq 1\}$  ,  $L_{1}=\{a^{m}b^{n}c^{n}:m,n\geq 1\}$  1 $L_{1}=\{a^{m}b^{n}c^{n}:m,n\geq 1\}$ 1 1 $L_{1}=\{a^{m}b^{n}c^{n}:m,n\geq 1\}$ } {  $displaystyle L_{1$ } = \ { $a^{m}$  b $^{n}$  c $^{n$ } c^{n} {n} : $m$ ,  $n\geq$ 1\} $L_{1}=\{a^{m}b^{n}c^{n}:m,n\geq 1\}$  ( $L_{2}=\{a^{n}b^{n}c^{m}:m,n\geq 1\}$  2)  $L_{2}=\{a^{n}b^{n}c^{m}:m,n\geq 1\}$  2  $=$  {  $L_{2}=\{a^{n}b^{n}c^{m}:m,n\geq 1\}$   $L_{2}=\{a^{n}b^{n}c^{m}:m,n\geq 1\}$  n  $L_{2}=\{a^{n}b^{n}c^{m}:m,n\geq 1\}$ n $L_{2}=\{a^{n}b^{n}c^{m}:m,n\geq 1\}$  :  $L_{2}=\{a^{n}b^{n}c^{m}:m,n\geq 1\}$  : , n } , n  $L_{2}=\{a^{n}b^{n}c^{m}:m,n\geq 1\}$  {  $displaystylashle$  l $L_{2}=\{a^{n}b^{n}c^{m}:m,n\geq 1\}$ } {a } {a } {2 }

문자열 abcc, aabbc 및 aaabbccc를 지정하면 L과 L₂ 양쪽에₁ 속하는 문자열(즉, 비어 있지 않은 교차를 생성하는 유일한 문자열)은 aaabbccc인 것이 분명합니다.

기타 고려사항

통사적 술어를 사용하는 대부분의 형식어에서 술어의 구문은 비정사적, 즉 술어의 연산이 순서임을 의미한다.예를 들어, 위의 예제를 사용하여 다음과 같은 유사 함수를 고려합니다. 여기서 X ::= Y PRED Z는 "Y가 술어 Z도 만족하는 경우에만 X를 생성한다"는 의미로 이해됩니다.

S ::= a X ::= Y PRED Z Y ::= a+ BNCN Z ::= ANBN c+ BNCN ::= b [BNCN] c ANBN ::= a [ANBN] b

문자열 aaaabbccc를 지정하면 Y가 최초로 충족되어야 하는 경우(및 과도한 구현을 전제로), S는 aX를 생성하고 X는 aaaabbccc를 생성하여 aaaabbccc를 생성합니다.Z가 먼저 충족되어야 하는 경우 ANBN은 aaaabbb를 생성하지 못하기 때문에 문법상 aaaabbc는 생성되지 않습니다.또한 Y 또는 Z(또는 둘 다)가 감소 시 취할 조치를 지정하는 경우(많은 파서의 경우처럼) 이러한 생산과 일치하는 순서에 따라 부작용이 발생하는 순서가 결정된다.시간에 따라 변화하는 형식주의는 이러한 부작용에 의존할 수 있습니다.

사용 예

앤티엘

Parr & Quong은^[5] 구문 술어의 예를 다음과 같이 제시합니다.

 상태: (선언.)? 선언.        표현      ;

이는 C++의 다음과 같은 비공식적^[6] 제약조건을 충족하기 위한 것입니다.

선언처럼 보이면 선언입니다.그렇지 않으면 선언입니다.
표현처럼 보이면 그렇다; 그렇지 않으면
구문 오류입니다.

규칙 통계의 첫 번째 생성에서 구문 술어(선언)는?는 선언이 해당 생산의 나머지 부분이 성공하기 위해 존재해야 하는 구문 컨텍스트임을 나타냅니다.(선언)의 용도를 해석할 수 있습니까?"선언이 일치할지 확신할 수 없습니다. 시험해 보고 일치하지 않으면 다음 대안을 시도해 보겠습니다."따라서 유효한 선언이 발견되면 규칙 선언이 두 번 인식됩니다.하나는 구문 술어로 인식되고 다른 하나는 의미적 액션을 실행하기 위한 실제 해석 중에 인식됩니다.

위의 예에서 주의할 점은 선언문 작성의 수용에 의해 트리거되는 코드는 술어가 충족될 경우에만 발생한다는 사실입니다.

표준 예

$L=\{a^{n}b^{n}c^{n}|n\geq 1\}$ L $L=\{a^{n}b^{n}c^{n}|n\geq 1\}$ { $L=\{a^{n}b^{n}c^{n}|n\geq 1\}$ $L=\{a^{n}b^{n}c^{n}|n\geq 1\}$ b $L=\{a^{n}b^{n}c^{n}|n\geq 1\}$ $L=\{a^{n}b^{n}c^{n}|n\geq 1\}$ $L=\{a^{n}b^{n}c^{n}|n\geq 1\}$ 1 $L=\{a^{n}b^{n}c^{n}|n\geq 1\}$ } { $displaystyle$ L = \ { $a ^$ { $n } b$ ^ { n } $c^$ { n $}$ n \ geq 1 \ } 은 $L=\{a^{n}b^{n}c^{n}|n\geq 1\}$ 다음과 같이 다양한 문법 및 형식으로 나타낼 수 있습니다.

표현식 구문 분석

 S ← &(A !b) a+ B !c  A ← a A? b  B ← b B? c

§ - 계산

바운드 술어 사용:

S → {A}^B

A → X 'c+' X → 'a' [X] 'b' B → 'a+' Y → 'b' [Y] 'c'

두 개의 자유 술어 사용:

A → <'a+'>_a <'b+'>_b ψ(a b)^X <'c+'>_c ψ(b c)^Y

X → 'a' [X] 'b' Y → 'b' [Y] 'c'

접속 문법

(주: 다음 예시는 실제로 L $=$ { $L=\{a^{n}b^{n}c^{n}|n\geq 0\}$ $L=\{a^{n}b^{n}c^{n}|n\geq 0\}$ n $L=\{a^{n}b^{n}c^{n}|n\geq 0\}$ n n $L=\{a^{n}b^{n}c^{n}|n\geq 0\}$ 0 $}$ { $displaystyle$ L=\{ $a^{n}$ b $^{n} c^{n}$ n $\geq$ 0 $L=\{a^{n}b^{n}c^{n}|n\geq 0\}$ 을 $L=\{a^{n}b^{n}c^{n}|n\geq 0\}$ 하지만, 결합문법의 발명자가 제시한 예이기 때문에 여기에 포함되어 있습니다.)^[7]:

S → AB&DC A → aA b B → bBc c C → cC d D → aDb ε

Perl 6 규칙

 규칙 S {<A> <!before b>> a+ <B> <!before c> } 규칙 A {a <A>?b } 규칙 B {B <B>?c }

구문적 술어를 사용하는 파서/형식 표현

완전한 목록은 아니지만 다음 구문 및 문법 형식에서는 구문 술어를 사용합니다.

ANTLR(Parr & Quong): 원래 ^[2]구현된 것처럼 구문 술어는 생산의 가장 왼쪽에 있으므로 구문 술어가 입력 스트림의 다음 부분을 먼저 받아들이는 경우에만 술어의 오른쪽에 있는 생산이 시도됩니다.술어는 순서가 매겨지지만 먼저 체크되고 술어가 충족되는 경우에만 절의 파싱이 속행되며 의미 액션은 비 ^[5]술어로만 발생합니다.
증강 패턴 매처(발마스): Balmas는 APM에 ^[8]관한 논문에서 구문적 술어를 "다단계 일치"라고 언급했습니다.APM 파서는 서브스트링을 변수에 바인드하고 나중에 이 변수를 다른 규칙과 비교하여 체크할 수 있습니다.이 경우 서브스트링이 추가 규칙에서 허용 가능한 경우에만 해석을 계속합니다.
구문 분석 식 문법(Ford): Ford의 PEGs는 And-predicate와 not-predicate로 ^[9]표현되는 구문적 술어를 가지고 있다.
γ-계산기(잭슨): γ-Calculus에서 구문 술어는 원래 단순 술어라고 불리지만 나중에 각각 다른 입력 ^[10]특성을 가진 바인딩 형식과 자유 형식으로 구분됩니다.
라쿠 규칙: Raku는 Perl 5의 정규 표현 ^[11]구문의 확장인 규칙이라고 불리는 문법을 기술하기 위한 일반화된 도구를 도입했습니다.술어는 앞에서 호출한 룩어헤드메커니즘을 통해 도입됩니다.<before ...>" 또는<!before ...>(즉, "이전에는" 안 된다.)Perl 5에는 이러한 예측 기능이 있지만 Perl 5의 보다 제한된 regexp 기능만 캡슐화할 수 있습니다.
ProGrammar (NorKen Technologies): ProGrammar의 GDL(Grammar Definition Language)은 구문적 술어를 해석 ^[12]제약이라고 하는 형태로 사용합니다.주의사항:이 링크는 더 이상 유효하지 않습니다!
연결 및 부울 문법(Okhotin): Okhotin에 ^[13]의해 처음 도입된 접속문법은 접속사 사전의 명확한 개념을 도입한다.접속어 및 부울어^[14] 문법의 후술은 지금까지의 형식주의의 가장 철저한 치료이다.

레퍼런스

^ Parr, Terence (2007). The Definitive ANTLR Reference: Building Domain-Specific Languages. The Pragmatic Programmers. p. 328. ISBN 978-3-540-63293-1.
^ ^a ^b Parr, Terence J.; Quong, Russell (October 1993). "Adding Semantic and Syntactic Predicates to LL(k) parsing: pred-LL(k)". Army High Performance Computing Research Center Preprint No. 93-096: 263–277. CiteSeerX 10.1.1.26.427. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
^ 를 클릭합니다Bar-Hillel, Y.; Perles, M.; Shamir, E. (1961). "On formal properties of simple phrase structure grammars". Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung. 14 (2): 143–172..
^ Hartmanis, Juris (1967). "Context-Free Languages and Turing Machine Computations". Proceedings of Symposia in Applied Mathematics. Mathematical Aspects of Computer Science. AMS. 19: 42–51. doi:10.1090/psapm/019/0235938. ISBN 9780821867280.
^ ^a ^b Parr, Terence; Quong, Russell (July 1995). "ANTLR: A Predicated-LL(k) Parser Generator" (PDF). Software: Practice and Experience. 25 (7): 789–810. doi:10.1002/spe.4380250705. S2CID 13453016.
^ Stroustrup, Bjarne; Ellis, Margaret A. (1990). The Annotated C++ Reference Manual. Addison-Wesley. ISBN 9780201514599.
^ Okhotin, Alexander (2001). "Conjunctive grammars" (PDF). Journal of Automata, Languages and Combinatorics. 6 (4): 519–535. doi:10.25596/jalc-2001-519. S2CID 18009960. Archived from the original (PDF) on 26 June 2019.
^ Balmas, Françoise (20–23 September 1994). "An Augmented Pattern Matcher as a Tool to Synthesize Conceptual Descriptions of Programs". Proceedings KBSE '94. Ninth Knowledge-Based Software Engineering Conference. Proceedings of the Ninth Knowledged-Based Software Engineering Conference. Monterey, California. pp. 150–157. doi:10.1109/KBSE.1994.342667. ISBN 0-8186-6380-4.
^ Ford, Bryan (September 2002). Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking (Master’s thesis). Massachusetts Institute of Technology.
^ Jackson, Quinn Tyler (March 2006). Adapting to Babel: Adaptivity & Context-Sensitivity in Parsing. Plymouth, Massachusetts: Ibis Publishing. CiteSeerX 10.1.1.403.8977.
^ Wall, Larry (2002–2006). "Synopsis 5: Regexes and Rules".
^ "Grammar Definition Language". NorKen Technologies.
^ Okhotin, Alexander (2000). "On Augmenting the Formalism of Context-Free Grammars with an Intersection Operation". Proceedings of the Fourth International Conference "Discrete Models in the Theory of Control Systems" (in Russian): 106–109.
^ Okhotin, Alexander (August 2004). Boolean Grammars: Expressive Power and Algorithms (Doctoral thesis). Kingston, Ontario: School of Computing, Queens University.

외부 링크

[1] Parr, Terence (2007). The Definitive ANTLR Reference: Building Domain-Specific Languages. The Pragmatic Programmers. p. 328. ISBN 978-3-540-63293-1.

[Parr&Quong1993-2] Parr, Terence J.; Quong, Russell (October 1993). "Adding Semantic and Syntactic Predicates to LL(k) parsing: pred-LL(k)". Army High Performance Computing Research Center Preprint No. 93-096: 263–277. CiteSeerX 10.1.1.26.427. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[3] 를 클릭합니다Bar-Hillel, Y.; Perles, M.; Shamir, E. (1961). "On formal properties of simple phrase structure grammars". Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung. 14 (2): 143–172..

[4] Hartmanis, Juris (1967). "Context-Free Languages and Turing Machine Computations". Proceedings of Symposia in Applied Mathematics. Mathematical Aspects of Computer Science. AMS. 19: 42–51. doi:10.1090/psapm/019/0235938. ISBN 9780821867280.

[Parr&Quong1995-5] Parr, Terence; Quong, Russell (July 1995). "ANTLR: A Predicated-LL(k) Parser Generator" (PDF). Software: Practice and Experience. 25 (7): 789–810. doi:10.1002/spe.4380250705. S2CID 13453016.

[Stroustrup&Ellis1990-6] Stroustrup, Bjarne; Ellis, Margaret A. (1990). The Annotated C++ Reference Manual. Addison-Wesley. ISBN 9780201514599.

[Okhotin2001-7] Okhotin, Alexander (2001). "Conjunctive grammars" (PDF). Journal of Automata, Languages and Combinatorics. 6 (4): 519–535. doi:10.25596/jalc-2001-519. S2CID 18009960. Archived from the original (PDF) on 26 June 2019.

[Balmas1994-8] Balmas, Françoise (20–23 September 1994). "An Augmented Pattern Matcher as a Tool to Synthesize Conceptual Descriptions of Programs". Proceedings KBSE '94. Ninth Knowledge-Based Software Engineering Conference. Proceedings of the Ninth Knowledged-Based Software Engineering Conference. Monterey, California. pp. 150–157. doi:10.1109/KBSE.1994.342667. ISBN 0-8186-6380-4.

[Ford2002-9] Ford, Bryan (September 2002). Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking (Master’s thesis). Massachusetts Institute of Technology.

[Jackson2006-10] Jackson, Quinn Tyler (March 2006). Adapting to Babel: Adaptivity & Context-Sensitivity in Parsing. Plymouth, Massachusetts: Ibis Publishing. CiteSeerX 10.1.1.403.8977.

[Wall2002-11] Wall, Larry (2002–2006). "Synopsis 5: Regexes and Rules".

[NorKen-12] "Grammar Definition Language". NorKen Technologies.

[Okhotin2000-13] Okhotin, Alexander (2000). "On Augmenting the Formalism of Context-Free Grammars with an Intersection Operation". Proceedings of the Fourth International Conference "Discrete Models in the Theory of Control Systems" (in Russian): 106–109.

[Okhotin2004-14] Okhotin, Alexander (August 2004). Boolean Grammars: Expressive Power and Algorithms (Doctoral thesis). Kingston, Ontario: School of Computing, Queens University.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Search