What Is Parsing? Definition and Examples in English Grammar
Parsing is a grammatical exercise that involves breaking down a text into its component parts of speech with an explanation of the form, function, and syntactic relationship of each part so that the text can be understood. The term "parsing" comes from the Latin pars for "part (of speech)."
In contemporary linguistics, parsing usually refers to the computer-aided syntactic analysis of language. Computer programs that automatically add parsing tags to a text are called parsers.
Key Takeaways: Parsing
Parsing is the process of breaking down a sentence into its elements so that the sentence can be understood.
Traditional parsing is done by hand, sometimes using sentence diagrams. Parsing is also involved in more complex forms of analysis such as discourse analysis and psycholinguistics.
Parse Definition
In linguistics, to parse means to break down a sentence into its component parts so that the meaning of the sentence can be understood. Sometimes parsing is done with the help of tools such as sentence diagrams (visual representations of syntactical constructions). When parsing a sentence, the reader takes note of the sentence elements and their parts of speech (whether a word is a noun, verb, adjective, etc.). The reader also notices other elements such as the verb tense (present tense, past tense, future tense, etc.).
Syntax Analyzer는 영어 문장의 다양한 구문을 자동으로 분석해 주고, 원하는 형태로 구문을 편집할 수 있는 웹 어플리케이션입니다
언어학에서 구문 분석(構文分析, 문화어: 구문해석, 문장해석) 또는 '파싱'은 문장을 그것을 이루고 있는 구성 성분으로 분해하고 그들 사이의 위계 관계를 분석하여 문장의 구조를 결정하는 것을 말한다.
컴퓨터 과학에서 파싱((syntactic) parsing)은 일련의 문자열을 의미있는 토큰(token)으로 분해하고 이들로 이루어진 파스 트리(parse tree)를 만드는 과정을 말한다.
영어 구문 분석의 효율 개선을 위한 3단계 구문 분석 Three-Phase English Syntactic Analysis for Improving the Parsing Efficiency
영어 구문 분석기는 영한 기계번역 시스템의 성능에 가장 큰 영향을 미치는 부분이다.
본 논문에서의 영어 구문 분석기는 규칙 기반 영한기계번역 시스템의 한 부분으로서, 많은 구문 규칙을 구축하고 차트 파싱 기법으로 구문 분석을 수행한다. 구문 규칙의 수가 많기 때문에 구문분석 과정에서 많은 구조가 생성되는데, 이로 인해 구문 분석 속도가 저하되고 많은 메모리를 필요로 하여 번역의 실용성이 떨어진다.
또한 쉼표를 포함하는 긴 문장들은 구문 분석 복잡도가 매우 높아 구문 분석 시간/공간 효율이 떨어지고 정확한 번역을 생성하기 매우 어렵다. 본 논문에서는 실제 생활에서 나타나는 긴 문장들을 효율적으로 번역하기 위해 문장 분할 방법을 적용한 3단계 구문 분석 방법을 제안한다.
구문 분석의 각 단계는 독립된 구문 규칙들을 적용하여 구문 분석을 수행함으로써 구문 분석의 복잡도를 줄이려 하였다. 이를 위해 구문 규칙을 3가지부류로 분류하고 이를 이용한 3단계 구문 분석 알고리즘을 고안하였다. 특히 세 번째 부류의 구문 규칙은 쉼표로 구성되는 문장 구조에 대한규칙으로 구성되는데, 이들 규칙들을 말뭉치의 분석을 통해 획득하는 방법을 제안하여 구문 분석의 적용률을 지속적으로 개선하고자 하였다.
실험을 통해 제안한 방법이 문장 분할만을 적용한 기존 2단계 구문 분석 방법에 비해 유사한 번역 품질을 유지하면서도 시간/공간 효율 면에서우수함을 확인하였다.
The performance of an English-Korean machine translation system depends heavily on its English parser.
The parser in this paper is a part of the rule-based English-orean MT system, which includes many syntactic rules and performs the chart-based parsing.
The parser generates too many structures due to many syntactic rules, so much time and memory are required.
The rule-based parser has difficulty in analyzing and translating the long sentences including the commas because they cause high parsing complexity.
In this paper, we propose the 3-hase parsing method with sentence segmentation to efficiently translate the long sentences appearing in usual.
Each phase of the syntactic analysis applies its own independent syntactic rules in order to reduce parsing complexity.
For the purpose, we classify the syntactic rules into 3 classes and design the 3-phase parsing algorithm.
Especially, the syntactic rules in the 3rd class are for the sentence structures composed with commas.
We present the automatic rule acquisition method for 3rd class rules from the syntactic analysis of the corpus, with which we aim to continuously improve the coverage of the parsing.
The experimental results shows that the proposed 3-phase parsing method is superior to the prior parsing method using only intra-sentence segmentation in terms of the parsing speed/memory efficiency with keeping the translation quality.
어휘분석과 구문분석(Lexical and Syntax Analysis)
글 : 서노리
구문 분석(Syntax analysis) 과정은 BNF에 기반하는데 이는 명확, 간결하고 paser의 기초가 되며 유지보수가 용이하다는 장점이 있기 때문이다.
구문 분석은 Lexical analyzer와 Syntax analzer(Parser) 두 가지 부분으로 구성된다.
이들이 분리되어 있는 이유는 다음과 같은 이유가 있다.
단순성(Simplicity) : 어휘 분석이 상대적으로 단순해서 분리 후 더 단순해질 수 있음
효율성(Efficiency) : 어휘 분석이 전체 컴파일 시간의 큰 부분을 차지하기 때문에 최적화가 필요하지만 구문 분석기는 최적화가 필요 없기 때문에 분리가 효과적
Lexical analysis(어휘 분석) Lexical analyzer(어휘 분석기)는 일종의 패턴 매칭기로 문자들을 모아서 논리적인 단위로 그룹핑을하는데, 이들을 lexemes 또는 token이라고 한다. 이렇게 구분된 token들에 에러가 있는지 검사하고 또한 문자열에서 공백을 제거하기도 한다.
※ 어휘 분석기를 구성하는 방법 - State Diagram(상태 전이 다이어그램)
Syntax analysis(구문 분석) Syntax analysis는 파싱(Parsing)이라고도 하며 expression, statement, program unit 단위로 문법 검사를 하며 해당 입력의 AST(추상 구문 트리)를 생성하여 반환한다.
※ AST(추상 구문 트리)란?
- 입력 스트링의 구문 구조를 추상적으로 보여주는 트리
- 일반적인 Syntax tree(parse tree)에서 부가 정보를 제거한 tree
※ 파싱의 목적
모든 syntax error를 찾는 것 AST를 생성하는 것
Parser의 종류 Top-down Parser - root부터 아래로 내려가면서 parse tree를 생성 - leftmost derivation을 기반으로함 - RD Parser와 LL Parser가 있음 - Left Recursion Problem이 존재함
Bottom-up Parser - leaf부터 root까지 올라가면서 parse tree를 생성 - rightmost derivation의 역순으로 진행됨 - LR Parser가 있음 - Top-down parser보다 더 좋은 성능을 보임
RD Parser(Recursive-Descent Parser) - nonterminal 당 각각의 함수를 만들어서 이들을 재귀적으로 호출하며 parse tree를 생성하는 방식 - EBNF에 이상적으로 적합하다. (BNF보다 더 적은 nonterminal을 사용할 수 있기 때문)
RHS의 각각의 terminal symbol들에 대해서는 그 값들을 처리해주면 되고 nonterminal symbol들에 대해서는 각각의 함수를 호출함으로써 nonterminal symbol을 처리한다.
※ Top-down Parser의 문제점 1 - Left Recursion Problem
A -> Aa | ... 또는 A -> B B -> A 와 같은 문법들은 left recursion이 발생할 수 있다. 이러한 문장들은 Top-down parser로 구현이 불가능하다. 따라서 이런 경우 BNF 자체를 바꾸거나 Bottom-up parser로 구현해야 한다.
각각의 nonterminal symbol에 대해서 RHS이 두 개 이상일 때, 가장 먼저 나오는 terminal이 서로 같아서는 안된다는 것이다. 가장 먼저 나오는 terminal이 같은 경우 Top-down parser로 구현이 불가능하다. 이런 경우 Left facotring을 통해서 해결할 수 있다.
- Left factoring
새로운 nonterminal을 정의하여 문제를 해결할 수 있다
※ Bottom-up Parser 개념 용어
handle : rightmost의 역순으로 올 수 있는 nonterminal과 terminal의 조합 handle은 simple phrase에 해당한다.
phrase : 부분 parse tree의 모든 잎 노드들로 구성된 문자열(여러 번의 derivation)
simple phrase : 단 한 번의 derivation을 통해서 만들어진 어구
바텀업 파싱은 handle pruning의 과정이라고 생각할 수 있다.
LR Parser - parsing table, stack, input buffer로 이루어짐
- 효율적이고 거의 모든 문법에서 동작
- Shift-Reduce Algorithm을 사용
※ Shift-Reduce Algorithm의 Action Table 해석 방법
Shift '숫자' : input에서 symbol을 하나 읽어서 stack에 저장한 후 state를 '숫자'로 변경 Reduce '숫자' : '숫자'에 해당하는 rule에 따라 오른쪽 symbol을 왼쪽 symbol로 변경한 후, Goto Table로부터 state를 결정 Accept : 에러 없이 파싱이 끝났음을 의미 빈칸 : 에러가 발생함을 의미