파싱 (Parsing) (構文解析)에 대해

構文解析（こうぶんかいせき、Syntactic Analysis）とは、ある文章の文法的な関係を説明すること(parse)。計算機科学の世界では、構文解析は字句解析（Lexical Analysis）とともに、コンピュータ言語などの形式言語の解析に使用される。また、自然言語処理に応用されることもある。

構文解析を行う機構を構文解析器（Parser）と呼ぶ。

 

구문 분석 (行文분석, Syntactic Analysis)은 한 문장의 문법적인 관계를 설명하는 것(parse)이다. 컴퓨터 과학의 세계에서 구문 분석은 어휘 분석 (Lexical Analysis)과 함께 컴퓨터 언어 등의 형식 언어 분석에 사용된다. 또한 자연 언어 처리에 응용 될 수있다.

구문 분석을 실시하는 기구를 구문 분석기 (Parser)라고 부른다.

 

一般的に、プログラムにおける構文解析では、コンピュータ言語などの形式言語で記述された入力から、字句解析を通してトークン列を受け取り、構文木や抽象構文木のようなデータ構造を生成し、その後の処理に渡す。構文解析と同時に、目的の処理をおこなってしまう場合もある。

 

일반적으로 프로그래밍에서의 구문 분석에서는 컴퓨터 언어 등의 형식 언어로 기술된 입력에서 어휘 분석을 통해 토큰 열을 받아 파서 트리와 추상 구문 트리와 같은 데이터 구조를 생성 한 다음 처리하여 넘긴다. 구문 분석과 동시에 원하는 처리를 행해 버리는 경우도 있다.

 

プログラミング言語の場合、実用上、プログラムとして正しい入力のみを受け付けるような構文規則を定めることは現実的でない。そのため、一般に構文解析器は制約を弱めて本来の言語の文法よりも広い範囲の構文を受け付け（つまり、不正な構文も受け付ける）、後で不正なものを排除するようにすることが多い。

構文解析器を一から作るのではなく、パーサジェネレータで生成することも広く行われている。

 

프로그래밍 언어의 경우, 실질적인 프로그램으로 올바른 입력 만 허용하도록 구문 규칙을 정하는 것은 현실적이지 못하다. 따라서 일반적으로 구문 분석기는 제약을 약화 본래 언어의 문법보다 넓은 범위의 구문을 접수 (즉, 부정한 구문도 접수) 나중에 잘못된 것을 배제하도록 하는 경우가 많다.

구문 분석기를 처음부터 만드는 것이 아니라 파서 생성기 로 생성 할 수도 널리 이용되고 있다.

 

 

처리 개요

 

以下では、字句文法と構文文法という2段階の文法を持つコンピュータ言語の構文解析を例として説明する。

 

다음은 어휘 문법과 구문 문법이라는 2 단계의 문법을 가진 컴퓨터 언어의 구문 분석을 예로 설명한다.

 

まず第一段階として字句（トークン）を生成する。これを字句解析と呼ぶ。入力文字列は正規表現による文法で定義された意味のあるシンボルに分割される。例えば、電卓プログラムに "12*(3+4)^2" と入力されたとき、これを 12, *, (, 3, +, 4, ), ^, 2 という字句（トークン）に分割する。各トークンは電卓プログラムの数式として意味のあるシンボルである。字句解析を含む構文解析器は *, +, ^, (, ) といった文字が新たなトークンの先頭になるという規則を持っているため、"12*" や "(3" といった無意味な字句の切り分けは発生しない。

 

첫째 단계로 자구(토큰)를 생성한다. 이것을 어휘 분석이라고 부른다. 입력 문자열은 정규표현에 의한 문법에 정의되어 의미 있는 기호로 분할된다. 예를 들어, 계산기 프로그램 "12 * (3 + 4) ^ 2"를 입력했을 때 이를 12 * (3 + 4), ^ 2라는 문구 (토큰)로 나눕니다. 각 토큰은 계산기 프로그램의 수식으로 의미 있는 상징이다. 어휘 분석을 포함 구문 분석기는 * + ^ (,) 등의 문자가 새로운 토큰의 시작된다는 규칙을 가지고 있기 때문에 "12 *"또는 "(3"등 무의미한 어휘 분리는 발생하지 않는다.

 

次の段階で実際の構文解析を行う。構文解析では、トークンの並びが文法に照らして正しい表現となっているかを判定する。このため、文脈自由文法を参照して再帰的に規則を適用していく。ただし、プログラミング言語の構文規則は文脈自由文法だけでは表現できない。例えば、データ型が正しいか、識別子の宣言が正しいかなどは文脈自由文法の範囲外の話である。そのような規則は形式的には属性文法で表される。

 

다음 단계에서 실제 구문 분석을 실시한다. 구문 분석에서는 토큰의 줄이 문법에 비추어 올바른 표현되고 있는지를 판정한다. 따라서 문맥 자유 문법을 참조 재귀적으로 규칙을 적용해 나간다. 그러나 프로그래밍 언어의 구문 규칙은 문맥 자유 문법만으로는 표현할 수 없다. 예를 들어, 데이터 유형이 올바른지 식별자의 선언이 정확한지 등은 문맥 자유 문법의 범위를 벗어난 얘기이다. 그런 규칙은 형식적으로는 속성 문법으로 표현된다.

 

最後に、意味的な解析が行われ、構文が確認された表現の意味を識別して、適当な行動をとる。電卓プログラムの場合、適当な行動とは式の評価（計算）であり、コンパイラならコードの生成である。属性文法もそのような行動決定に関与する。

마지막으로, 의미적인 해석을 구문이 확인 된 표현의 의미를 식별하여 적절한 행동을 취한다. 계산기 프로그램의 경우 적절한 행동과는 식의 평가 (계산)이며, 컴파일러라면 코드의 생성이다. 속성 문법도 그런 행동 결정에 관여한다.

 

 

방법

 

構文解析にはさまざまな手法が提案されており、それぞれの構文解析法に対して適用可能な文法の範囲が存在する。構文解析法は大まかに演算子順位法、トップダウン構文解析法、ボトムアップ構文解析法に分類でき、歴史的には、演算子順位法、トップダウン構文解析法は構文解析理論によって後から説明が加えられ、ボトムアップ構文解析法は理論主導で作成された。

 

구문 분석에는 다양한 방법이 제안되어 있으며, 각각의 구문 분석 방법에 적용가능한 문법의 범위가 존재한다. 구문 분석 방법은 대충 연산자 순위법 , 하향식 구문 분석 방법 , 상향식 파싱 방법으로 분류 할 수 있고, 역사적으로는 연산자 순위 법, 하향식 구문 분석 방법은 구문 분석 이론에 의해 나중에 설명이 추가된다. 상향식 파싱 법을 기준으로 작성되었다.

 

演算子順位法とトップダウン構文解析法の手続きは人力で作成されることがコンパイラの初期の時代にはあった。特に、トップダウン構文解析法である再帰下降構文解析法はそのプログラムの実際のコードが文法の記述によく一致することが知られている。しかし、一般にボトムアップ構文解析は非常に多くの内部状態とその間の遷移規則を必要とし、その手続きを人力で作成するのは困難である。

 

연산자 순위 법과 하향식 구문 분석 방법의 절차는 인력으로 작성 될 수 컴파일러의 초기 시대에는 있었다. 특히 하향식 구문 분석 방법 인 재귀 하강 파싱 법은 그 프로그램의 실제 코드가 문법 설명 잘 일치하는 것으로 알려져 있다. 그러나 일반적으로 상향식 구문 분석은 많은 내부 상태와 그 사이의 전이 규칙을 필요로 하고 그 절차를 인력으로 만드는 것은 곤란하다.

 

現在は、主にボトムアップ構文解析法であるLALR(1)を使用した構文解析器がパーサジェネレータによって生成されることが多い。この手法を使用するパーサジェネレータにはyaccやbisonなどがあり、どちらも代表的なパーサジェネレータである。これらのパーサジェネレータがこの手法を採用する理由としては、適用可能な文法範囲が十分に大きく、効率もそこそこ悪くないことなどが挙げられる。その他に、トップダウン構文解析法であるLL法が使用・生成される場合もままある。

현재는 주로 상향식 파싱 법이 많이 쓰인다. LALR(1)를 사용한 구문 분석기가 파서 생성기에 ​​의해 생성되는 경우가 많다. 이 기술을 사용하는 파서 생성기는 yacc 나 bison 등이 모두 대표적인 파서 생성기이다. 이러한 파서 생성기가 이 방식을 채택하는 이유는 적용 가능한 문법 범위가 충분히 크고 효율도 적당히 나쁘지 않은 것 등을 이유로 들 수 있다. 그밖에는 하향식 구문 분석 방법인 LL 법 이 사용되는 경우도 있다.

출처 : https://ja.wikipedia.org/wiki/%E6%A7%8B%E6%96%87%E8%A7%A3%E6%9E%90