Parsing and Ambiguity( 구문 분석 및 모호성 )
주어진 𝑮로부터 𝑳을 탐지하는 데 중점을 둔다.
멤버십 알고리즘 (membership algorithm)
- 단어 𝑤가 주어지면, 𝑤가 𝐿 𝐺에 포함되어 있는지 알고 싶다.
구문 분석 (Parsing)
- 𝑤가 𝐿 𝐺에 있다면, 𝑤의 유도를 찾는다.
- 𝑤 ∈ 𝐿(𝐺)가 유도되는 일련의 생성 규칙.
예제 문제
- 문법을 고려하십시오: 𝑆 → 𝑆𝑆 𝑎𝑆𝑏 𝑏𝑆𝑎 | 𝜆
- 문자열 𝑎𝑎𝑏𝑏는 𝐿 𝐺에 포함되어 있을까요?
- 만약 그렇다면, 문자열은 어떻게 유도될 수 있을까요?
모호성(Ambiguity)
- 어떤 문자열을 두 개 이상의 구문 분석 트리로 유도할 수 있는 문법은 모호하다고 합니다.
- 문법 𝑆 → 𝑎𝑆𝑏 𝑆𝑆 𝜆를 고려해보세요.
- 문자열 𝑎𝑎𝑏𝑏는 하나 이상의 구문 분석 트리로부터 유도될 수 있습니다.
- 유감스럽게도…
- 문맥 자유 문법에서 모호성을 제거하는 일반적인 알고리즘은 없습니다.
- 문맥 자유 문법이 모호한지 판단하는 알고리즘도 없습니다.
- 대신, 모호하지 않은 문법을 개발할 수 있습니다.
- 우선순위와 결합성을 사용하여.
모호성 제거 ( Eliminating ambiguity)
- 문법 𝐺 = (𝐸, 𝐼, 𝑎, 𝑏, 𝑐, +, ∗, (, ), 𝐸, 𝑃)를 고려하면 𝑃는 다음과 같이 주어집니다:
- 𝐸 → 𝐼
- 𝐸 → 𝐸 + 𝐸
- 𝐸 → 𝐸 ∗ 𝐸
- 𝐸 → (𝐸)
- 𝐼 → 𝑎 | 𝑏 | 𝑐
- 이 문법은 모호합니다.
- 문자열 𝑎 + 𝑏 ∗ 𝑐를 고려해보세요.
- 우리는 연산자의 우선순위를 정하여 모호성을 해결할 수 있습니다 (예: ∗는 +보다 우선합니다).
- 𝐸 → 𝑇
- 𝑇 → 𝐹
- 𝐹 → 𝐼
- 𝐸 → 𝐸 + 𝑇
- 𝑇 → 𝑇 ∗ 𝐹
- 𝐹 → (𝐸)
- 𝐼 → 𝑎 | 𝑏 | 𝑐
Context-Free Grammars and Programming Languages ( 문맥 자유 문법과 프로그래밍 언어)
CFG는 프로그래밍 언어를 표현하는 데 사용될 수 있습니다.
- 형식 언어 이론의 가장 중요한 용도 중 하나입니다.
- 프로그래밍 언어의 정의
- 인터프리터와 컴파일러의 구축
- 정규 언어
- 단순한 패턴의 인식
- 문맥 자유 언어
- 더 복잡한 측면을 모델링
바커스-나우르 표기법 ( Backus-Naur Form : BNF)
- 프로그래밍 언어에서 언어의 문법을 수학적 수식으로 표현하는 데 사용되는 형식입니다.
- 예:
- <expression> ∷= <term> | <expression> + <term>,
- <term> ∷= <factor> | <term> * <factor>, …
- 여기서 * 와 + 는 터미널 기호이며, "∷="은 "→"를 나타냅니다.
- 예: C 언어의 while 문
- <while_statement> ∷= while <expression> <statement>
문맥-자유 문법 (CFG)은 프로그래밍 언어를 파싱하는 데 사용될 수 있습니다.
<오학주 교수님의 강의 자료 중 발췌>
- ANTLR (https://www.antlr.org)
- 구조화된 텍스트나 바이너리 파일을 읽거나 파싱하기 위해 널리 사용되는 파서 생성기입니다.
- 문법에서 파싱 트리를 구성하고 걷는 파서를 생성합니다.
- LLVM (https://llvm.org)
- 인기 있는 언어들을 위한 파서를 포함한 컴파일러 도구 체인입니다.
