애매한 문법

Ambiguous grammar

컴퓨터 과학에서 애매한 문법은 문맥이 없는 문법으로, 애매하지 않은 문법은 문맥이 없는 문법으로, 문맥이 없는 문법은 문맥이 없는 문법으로, 문맥이 없는 문법은 모든 유효한 문자열이 고유한 왼쪽 유도나 해석 [1]트리를 가진다.많은 언어들이 애매모호하고 모호하지 않은 문법을 모두 인정하는 반면, 일부 언어들은 애매한 문법만 인정한다.비어 있지 않은 언어는 모호하지 않은 문법을 취하고 중복 규칙이나 동의어를 도입함으로써 애매한 문법을 허용한다(모호한 문법이 없는 유일한 언어는 빈 언어이다.애매한 문법만을 인정하는 언어를 본질적으로 애매한 언어라고 하며, 본질적으로 문맥이 없는 언어도 있습니다.결정론적 문맥이 없는 문법은 항상 모호하지 않고 모호하지 않은 문법의 중요한 하위 클래스입니다. 그러나 비결정론적 모호하지 않은 문법은 있습니다.

컴퓨터 프로그래밍 언어의 경우, 참조 문법이 종종 애매한 경우가 있는데, 그 이유는 매달림 또는 매달림 문제와 같은 문제 때문입니다.존재하는 경우, 이러한 모호성은 일반적으로 우선순위 규칙 또는 상황에 맞는 다른 구문 분석 규칙을 추가하여 해결되므로 문법은 전체적으로 [citation needed]모호하지 않습니다.일부[2] 구문 분석 알고리즘(얼리 또는 GLR 구문 분석기 등)은 구문적으로 [3]애매한 문자열에서 구문 분석 트리 세트(또는 "파스 포레스트")를 생성할 수 있습니다.

예

사소한 언어

가장 간단한 예는 빈 문자열로만 구성된 일반 언어에 대한 다음과 같은 애매한 문법(시작 기호 A)입니다.

A → A ε

…비단말기 A는 다시 그 자체 또는 빈 문자열로 유도할 수 있습니다.따라서 빈 문자열은 규칙 A → A의 사용 횟수에 따라 길이 1, 2, 3 및 실제로 임의의 길이의 가장 왼쪽 유도체를 가집니다.

또한 이 언어에는 단일 생산 규칙으로 구성된 명확한 문법이 있습니다.

A → ★

...즉, 고유한 프로덕션에서 생성할 수 있는 것은 언어 고유의 문자열인 빈 문자열뿐입니다.

마찬가지로 중복을 추가하여 비어 있지 않은 언어의 문법을 모호하게 만들 수 있습니다.

단항 문자열

예를 들어, 특정 문자의 단항 문자열의 정규 언어입니다.'a'(정규 표현)a*)에는 명확한 문법이 있습니다.

A → aA »

…하지만 문법도 애매합니다.

A → aA Aa »

이는 (명확한 문법을 위해) 오른쪽 연관 트리를 생성하거나 왼쪽 및 오른쪽 연관성을 모두 허용하는 것에 해당합니다.이하에 상술합니다.

덧셈과 뺄셈

문맥 자유 문법

A → A + A - A

는 문자열 a + a + a의 왼쪽 끝에2개의 파생이 있기 때문에 애매합니다.

A → A + A A → A + A
→ a + A → A + A + A (첫 번째 A는 A+A로 대체됨)두 번째 A를 교체해도 유사한 파생이 발생한다.)
→ a + A + A → a + A + A
→ a + a + A → a + a + A
→ a + a + a → a + a + a

다른 예로는 문자열 a + a - a에 대해 2개의 해석 트리가 있기 때문에 문법이 모호합니다.

Leftmostderivations jaredwf.svg

그러나 이 언어가 생성하는 언어는 본질적으로 애매한 것은 아닙니다.다음은 같은 언어를 생성하는 애매하지 않은 문법이 있습니다.

A → A + A - a

달랑달리다

주요 기사: 행글링 기타

컴퓨터 프로그래밍 언어에서 모호성의 일반적인 예로는 매달림 또는 매달림 문제입니다.많은 언어에서elseIf-then(–else) 스테이트먼트는 옵션입니다.그러면 내포조건은 문맥이 없는 문법에 따라 여러 가지 방법으로 인식됩니다.

구체적으로는 많은 언어에서 조건문을 if-then 형식과 if-then-else 형식이라는 두 가지 유효한 형식으로 작성할 수 있으며, other 절은 [note 1]선택사항입니다.

규칙을 포함하는 문법에서

스테이트먼트 → 조건이 있으면 스테이트먼트, 조건이 있으면 스테이트먼트, 그렇지 않으면 스테이트먼트...상태 → ...

일부 애매한 구문이 나타날 수 있습니다.표현

a의 경우 b의 경우 s2의 경우

둘 중 하나로 해석할 수 있다

a가 시작되면 b가 시작하고, 다른 s2가 종료됩니다.

또는 로서

a가 개시되면 b가 개시되면 s2가 종료된다.

의 유무에 따라else첫 번째와 관련되어 있습니다.if두 번째 또는 두 번째if.

이것은 다양한 언어로 다양한 방법으로 해결됩니다.때때로 문법은 모호하지 않게 수정된다. 예를 들어, 예를 들어, 다음과 같이endif진술 또는 작성else의무적인.다른 경우에 문법은 모호하게 남지만, 문법은 문맥에 따라 전체적으로 문맥에 민감하게 만들면서 모호성은 해결된다.else가장 가까운 곳에if후자의 경우 문법은 모호하지 않지만 문맥이 없는 문법은 [clarification needed]모호합니다.

다중 파생된 명확한 문법

같은 문자열의 여러 파생물이 존재한다고 해서 문법이 애매하다는 것을 나타내는 것은 아닙니다.왼쪽 끝의 파생물(또는 동등하게 복수의 해석 트리)만이 애매함을 나타냅니다.

예를 들어, 간단한 문법은

S → A + A → 0 1

는 언어 {0+0, 0+1, 1+0, 1+1}의 명확한 문법입니다.이들 4개의 문자열은 각각 왼쪽 끝의 파생만 가지지만, 예를 들어 두 개의 다른 파생이 있습니다.

S a A + A 0 0 + A 0 0 + 0

그리고.

S a A + A a A + 0 0 0 + 0

이전 파생 모델만 가장 왼쪽에 있습니다.

애매한 문법 인식

임의의 문법이 애매한지 아닌지에 대한 판단 문제는 그것이 포스트 대응 [4]문제와 동등하다는 것을 보여줄 수 있기 때문에 판단할 수 없다.적어도 문맥이 없는 [5]문법의 애매성을 검출하기 위한 몇 가지 반판정 절차를 실행하는 툴이 있다.

문맥이 없는 문법의 해석 효율은 문맥을 받아들이는 자동화에 의해 결정됩니다.결정론적 컨텍스트 프리 문법은 결정론적 푸시다운 오토마타에 의해 받아들여지며, 예를 들어 LR [6]파서에 의해 선형 시간으로 해석될 수 있다.이들은 컨텍스트 프리 문법의 엄밀한 서브셋으로, 푸시다운 오토마타에 의해 받아들여지고 다항식 시간, 예를 들어 CYK 알고리즘에 의해 해석될 수 있습니다.

명확한 문맥이 없는 문법은 비결정적일 수 있습니다.예를 들어, 알파벳 0과 1의 짝수 길이 회문 언어에는 명확한 문맥이 없는 문법 S → 0S0 1S1 ε가 있다. 이 언어의 임의의 문자열은 모든 기호를 먼저 읽지 않으면 구문 분석될 수 없으며, 이는 푸시다운 오토마톤이 다른 포지션을 수용하기 위해 대체 상태 전환을 시도해야 한다는 것을 의미한다.sible lengths (반파싱 [7]문자열의 sible 길이)

그럼에도 불구하고, 문법의 모호성을 제거하는 것은 결정론적 문맥 없는 문법을 만들어 낼 수 있고, 따라서 더 효율적인 파싱을 가능하게 할 수 있다.YACC와 같은 컴파일러 생성기에는 우선순위 및 연관성 제약 조건을 사용하는 등 일부 종류의 모호성을 해결하기 위한 기능이 포함되어 있습니다.

본질적으로 애매한 언어

본질적으로 모호한 언어의 존재는 1961년 MIT 연구보고서에서 [8]Rohit Parikh에 의해 Parikh의 정리로 증명되었다.

일부 문맥이 없는 언어(문법에 의해 생성될 수 있는 문자열 집합)는 모호한 문법과 모호한 문법을 모두 가지고 있지만, 모호한 문맥이 없는 문법은 존재할 수 없는 문맥이 없는 언어가 존재합니다.{오빠 bmcmd와 n, m>0}{\displaystyle\와 같이{a^{n}b^{m}c^{m}d^{n}n,m&gt의{오빠 b와 cmdmn, m>0}{\displaystyle\와 같이{a^{n}b^{n}c^{m}d^{m}n,m&gt을 가진 본질적으로 모호한 언어의 예입니다;0\}};0\}}. 이 세트, 두 context-fr의 노조 문맥 자유다.ee 언어는 항상 콘텍스트가 없습니다.단, Hopcroft & Ullman(1979)은 (문맥이 없는) 공통 d > 0}({ c^{ d n0[9]의 문자열을 명확하게 해석하는 방법은 없음을 증명합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Willem J. M. Levelt (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. ISBN 978-90-272-3250-2.
  2. ^ Scott, Elizabeth (April 1, 2008). "SPPF-Style Parsing From Earley Recognizers". Electronic Notes in Theoretical Computer Science. 203 (2): 53–67. doi:10.1016/j.entcs.2008.03.044.
  3. ^ 토미타 마사루"효율적인 증강 컨텍스트 없는 구문 분석 알고리즘입니다."컴퓨터 언어학 13.1-2(1987년): 31-46.
  4. ^ Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey (2001). Introduction to automata theory, languages, and computation (2nd ed.). Addison-Wesley. Theorem 9.20, pp. 405–406. ISBN 0-201-44124-1.
  5. ^ Axelsson, Roland; Heljanko, Keijo; Lange, Martin (2008). "Analyzing Context-Free Grammars Using an Incremental SAT Solver" (PDF). Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP'08), Reykjavik, Iceland. Lecture Notes in Computer Science. Vol. 5126. Springer-Verlag. pp. 410–422. doi:10.1007/978-3-540-70583-3_34. ISBN 978-3-540-70582-6.
  6. ^ Knuth, D. E. (July 1965). "On the translation of languages from left to right". Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2.
  7. ^ Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey (2001). Introduction to automata theory, languages, and computation (2nd ed.). Addison-Wesley. pp. 249–253. ISBN 0-201-44124-1.
  8. ^ Parikh, Rohit (January 1961). Language-generating devices. Quarterly Progress Report, Research Laboratory of Electronics, MIT.
  9. ^ 페이지 99-103, 제4.7

메모들

  1. ^ 다음 예제에서는 Pascal 구문을 사용합니다.

외부 링크

  • dk.brics.brics: 문법 모호성 분석기.
  • CFGAnalyzer - 언어 보편성, 모호성 및 유사한 속성과 관련하여 문맥이 없는 문법을 분석하기 위한 도구입니다.