파싱

구문 분석 , 구문 분석 , 또는 구문 분석 분석하는 과정입니다 문자열 의 문자 중 하나로, 자연 언어 , 컴퓨터 언어 또는 데이터 구조 (a)의 규정에 부합하는, 형식적인 문법 . 파싱 ( parsing ) 이라는 용어 는 라틴어 파스 ( orationis )에서 유래 한 것으로 음성의 일부를 의미 합니다. [1] 용어는 언어학 과 컴퓨터 과학 의 다른 분야에서 약간 다른 의미를 가지고 있습니다 . 전통적인 문장 분석은 종종 문장 다이어그램 과 같은 장치를 사용하여 문장이나 단어의 정확한 의미를 이해하는 방법으로 수행됩니다 . 보통 주제 와 술어 와 같은 문법 구분의 중요성을 강조합니다 . 내 컴퓨터 언어학 용어는 결과의 성분으로 단어의 문장이나 다른 문자열의 컴퓨터에 의해 형식적인 분석을 참조하는 데 사용됩니다 파스 트리 도 포함 할 수있는, 서로 자신의 구문 관계를 보여주는 의미 및 기타 정보를. 이 용어는 언어 이해를 설명 할 때 심리 언어학 에도 사용됩니다 . 이 문맥에서, 파싱은 인간이 "문법적 구성 요소, 말의 부분을 식별하는 것, 구문 적 관계 등"으로 문장 또는 구 (언어 또는 텍스트로)를 분석하는 방식을 말한다. [1] 이 용어는 화자가 정원 경로 문장 을 해석하는 데 도움이되는 언어 적 신호를 논의 할 때 특히 일반적 입니다. 컴퓨터 과학 내에서이 용어는 컴퓨터 언어 분석에 사용되며, 컴파일러 와 해석기 의 작성을 용이하게하기 위해 입력 코드를 구성 요소 부분으로 구문 분석하는 것을 말합니다 . 이 용어는 또한 분리 또는 분리를 설명하기 위해 사용될 수있다.

언어적 분석 방법

때때로로 알려진 구문 분석의 전통적인 문법 운동, 절 분석 , 형태, 기능에 대한 설명 및 각 부분의 통 사적 관계와 언론의 그 구성 부분으로 텍스트를 분해 포함한다. [2] 이것은 크게 활용되는 언어의 경우 상당히 복잡 할 수있는 언어의 활용 및 축소 에 대한 연구에서 결정 됩니다. 'man bites dog'와 같은 문구를 구문 분석하려면 단수 명사 'man'이 문장의 주제이고 동사 'bites'는 동사 '물기'의 현재 시제의 단수 인 세 번째 사람이며 단수 명사 'dog'은 문장의 대상입니다. 문장 도표 와 같은 기술 문장에서 요소 간의 관계를 나타내는 데 사용되기도합니다.

파싱은 영어권 세계에서 문법을 가르치는 데 중심이되었으며, 언어의 사용과 이해의 기본으로 널리 간주되었습니다. 그러나 이러한 기술에 대한 일반적인 가르침은 더 이상 최신이 아닙니다.

컵퓨터언어로 분석 방법

일부 기계 번역 및 자연어 처리 시스템에서, 인간 언어로 작성된 텍스트는 컴퓨터 프로그램에 의해 구문 분석됩니다. [3] 인간 언어 구조에는 상당한 모호성 이 있기 때문에 인간 문장은 프로그램에 의해 쉽게 파싱되지 않으며 , 그 사용은 잠재적으로 무한한 가능성 범위 사이에 의미 (또는 의미 ) 를 전달하는 것이지만 그 중 일부만이 특별한 경우. [4]따라서 발화 "Man bites dog"와 "Dog bites man"은 세부적으로 명확하지만 다른 언어에서는 "Man dog bites"로 표시 될 수 있습니다. 걱정. 일부 규칙을 준수하고 있음에도 불구하고 비공식적 인 행동을 설명하기위한 공식 규칙을 준비하는 것은 어렵습니다. [ 인용 필요 ]

자연어 데이터를 구문 분석하려면 먼저 사용할 문법 에 동의해야합니다 . 구문 선택은 언어 적 문제와 계산상의 문제 모두에 영향을받습니다 . 예를 들어 일부 구문 분석 시스템은 어휘 기능 문법을 사용 하지만 일반적으로이 유형의 문법 구문 분석은 NP-complete로 알려져 있습니다 . 머리 중심 구문 구조 문법 은 구문 분석 커뮤니티에서 인기가있는 또 다른 언어 형식주의이지만, 다른 연구 노력은 Penn Treebank 에서 사용되는 것과 같은 덜 복잡한 형식주의에 중점을 두었습니다 . 얕은 파싱명사구와 같은 주요 구성 요소의 경계만을 찾는 것을 목표로합니다. 언어 논쟁을 피하기위한 또 다른 대중적인 전략은 의존성 문법 분석입니다.

대부분의 현대적인 파서는 적어도 부분적으로 통계적입니다 . 즉, 그들은 이미 주석이 달린 (수동으로 파싱 된) 훈련 데이터 모음에 의존합니다. 이 접근법을 통해 시스템은 특정 상황에서 다양한 구성이 발생하는 빈도에 대한 정보를 수집 할 수 있습니다. (참고 기계 학습 .) 간단한 포함 사용되고 접근 PCFGs (확률 문맥 자유 문법), [5] , 최대 엔트로피 , [6] 및 신경망을 . [7] 가장 성공적인 시스템의 대부분은 어휘 통계를 사용 합니다. 즉, 관련된 단어의 정체성과품사 ). 그러나 이러한 시스템은 취약하다 overfitting 과 어떤 종류의 필요 스무딩 효과가있다. [ 인용 필요 ]

자연 언어에 대한 구문 분석 알고리즘은 프로그래밍 언어에 대해 수동으로 디자인 된 문법과 마찬가지로 'nice'속성을 가진 문법에 의존 할 수 없습니다. 앞에서 언급했듯이 일부 문법 형식은 계산 방식으로 구문 분석하기가 매우 어렵습니다. 일반적으로, 원하는 구조가 문맥 이없는 경우에도 , 문법에 대한 어떤 종류의 문맥이없는 근사가 제 1 패스를 수행하는 데 사용된다. 문맥없는 문법을 사용하는 알고리즘은 종종 CYK 알고리즘 의 일부 변형에 의존하며 , 일반적으로 시간을 절약하기 위해 분석을 제거 하는 휴리스틱 이 있습니다. ( 차트 구문 분석 참조 ) 그러나 일부 시스템은 예를 들어 시프트 타임의 선형 시간 버전을 사용하여 정확도를 위해 속도를 교환 합니다.연산. 파서가 많은 분석을 제안하고 다소 복잡한 시스템이 최선의 옵션을 선택 하는 다소 최근의 개발이 파싱 ​​리 랭킹 입니다. [ 표창장은 필요로했다 ] 시맨틱 파서는 그 의미의 표현으로 텍스트를 변환합니다. [8]

파서

파서(Parser)란 Compiler의 일부로서 원시 프로그램의 명령문이나 온라인 명령문, HTML 문서 등에서 Markup Tag 등을 입력으로 받아들여서 구분을 해석 할 수 있는 단위로 여러 부분으로 해석해 w는 역할을 한다. 즉 Compiler나 Interpreter에서 원시 프로그램을 읽어 들여, 그 문장이 구조를 알아내는 Parsing을 행하여 주는 프로그램이다. 파서는 입력 데이터를 얻어 (흔히 텍스트) 및 빌드 소프트웨어 구성 요소 데이터 구조를 종종 일종의 - 파스 트리 , 추상 구문 트리 또는 다른 계층 구조를 올바른 신택스를 확인하는 동안, 입력의 구조적 표현을 제공. 파싱은 다른 단계들에 선행하거나 이어질 수 있거나, 이들은 단일 단계로 결합 될 수있다. 파서 앞에는 종종 입력 문자 시퀀스에서 토큰을 생성 하는 별도의 어휘 분석기가 있습니다 . 또는 스캐너없이 구문 분석 할 수 있습니다 . 파서는 수동으로 프로그래밍되거나 파서 생성기에 의해 자동 또는 반자동으로 생성 될 수 있습니다. 구문 분석은 templating을 보완하여 형식화 된 출력 을 생성 합니다. 이들은 서로 다른 도메인에 적용될 수 있지만 종종 scanf / printf 쌍 또는 컴파일러의 입력 (프런트 엔드 파싱) 및 출력 (백엔드 코드 생성) 단계 와 같이 함께 나타납니다 . 파서에 대한 입력은 종종 일부 컴퓨터 언어의 텍스트 이지만, 자연어 텍스트 또는 구조화되지 않은 텍스트 데이터 일 수도 있습니다.이 경우 일반적으로 구문 분석 트리가 아닌 텍스트의 특정 부분 만 추출됩니다. 파서는 scanf 와 같은 매우 간단한 기능부터 C ++ 컴파일러 의 프론트 엔드 또는 웹 브라우저 의 HTML 파서 와 같은 복잡한 프로그램에 이르기까지 다양 합니다 . 간단한 구문 분석의 중요한 클래스는 정규 표현식을 사용하여 수행됩니다. 정규 표현식 그룹은 정규 언어를 정의합니다.및 해당 언어에 대한 파서를 자동으로 생성하여 텍스트의 패턴 일치 및 추출을 허용하는 정규식 엔진. 다른 맥락에서, 정규 표현식은 파싱 전에 출력이 사용되는 렉싱 단계로서, 파싱 전에 대신 사용된다. 파서의 사용은 입력에 따라 다릅니다. 데이터 언어의 경우, 파서는 종종 HTML 또는 XML 텍스트 로 읽기와 같은 프로그램의 파일 읽기 기능으로 발견됩니다 . 이러한 예는 마크 업 언어 입니다. 프로그래밍 언어 의 경우 파서는 컴파일러 또는 인터프리터 의 구성 요소 로, 컴퓨터 프로그래밍 언어 의 소스 코드 를 구문 분석하여 일부 형태의 내부 표현을 만듭니다. 파서는 컴파일러 프론트 엔드 의 핵심 단계입니다 . 프로그래밍 언어는 결정론적인 컨텍스트 프리 문법 으로 지정되는 경향이 있습니다.빠르고 효율적인 파서를 작성할 수 있기 때문입니다. 컴파일러의 경우 구문 분석 자체를 한 번 또는 여러 번 수행 할 수 있습니다 ( 원 패스 컴파일러 및 멀티 패스 컴파일러 참조) . 1 패스 컴파일러의 묵시적인 단점은 정방향 패스 동안 코드 재배치가 제공되고 현재 프로그램 세그먼트가 현재 인식 된 것으로 인식 된 경우 수정이 뒤로 적용되는 수정 을 추가하여 크게 극복 할 수 있습니다. 완료되었습니다. 이러한 수정 메커니즘이 유용한 예로는 프로그램 세그먼트가 완료 될 때까지 GOTO의 대상을 알 수없는 정방향 GOTO 문이 있습니다. 이 경우 수정의 적용은 GOTO의 대상이 인식 될 때까지 지연됩니다. 반대로, 역 GOTO는 위치가 이미 알려져 있기 때문에 수정이 필요하지 않습니다.문맥이없는 문법은 언어의 모든 요구 사항을 표현할 수있는 정도로 제한됩니다. 비공식적으로, 그 이유는 그러한 언어의 기억이 제한되어 있기 때문입니다. 문법은 임의로 긴 입력에 대한 구문의 존재를 기억할 수 없습니다. 예를 들어, 참조되기 전에 이름을 선언해야하는 언어에 필요합니다. 그러나이 제약 조건을 표현할 수있는보다 강력한 문법은 효율적으로 구문 분석 할 수 없습니다. 따라서 원하는 언어 구문의 수퍼 세트를 허용하는 (즉, 일부 유효하지 않은 구문을 허용하는) 컨텍스트가없는 문법에 대해 완화 된 구문 분석기를 작성하는 것이 일반적인 전략입니다. 나중에, 의미 론적 분석 (컨텍스트 분석) 단계 에서 원하지 않는 구성물을 걸러 낼 수있다 . 예를 들어, 파이썬 에서 다음은 구문 상 유효한 코드입니다.

파싱 과정

설명

다음 예는 문법과 문법의 두 가지 수준으로 컴퓨터 언어를 구문 분석하는 일반적인 경우를 보여줍니다. 첫 번째 단계는 토큰 생성 또는 어휘 분석으로 , 입력 문자 스트림이 정규 표현식 문법으로 정의 된 의미있는 기호로 분할됩니다 . 예를 들어, 계산기 프로그램은 "로 입력 보는 것 12 * (3 + 4)^2"및 토큰으로 분할 12, *, (, 3, +, 4, ), ^, 2연산 식의 문맥에서 의미있는 심벌이고, 각각. 렉서는 문자가 있음을 알려 규칙을 포함하는 것 *, +, ^, (및 )이렇게 의미 토큰 '과 같은 새로운 토큰의 시작을 표시 12*"또는" (3"생성되지 않습니다. 다음 단계는 구문 분석 또는 구문 분석으로, 토큰이 허용 가능한 표현을 형성하는지 확인합니다. 이는 일반적으로 표현을 구성 할 수있는 구성 요소와 해당 구성 요소가 나타나는 순서를 반복적으로 정의 하는 컨텍스트없는 문법 을 참조하여 수행 됩니다. 그러나 프로그래밍 언어를 정의하는 모든 규칙을 컨텍스트가없는 문법만으로 표현할 수있는 것은 아닙니다 (예 : 유형 유효성 및 적절한 식별자 선언). 이러한 규칙은 속성 문법 으로 공식적으로 표현할 수 있습니다 .마지막 단계는 시맨틱 파싱 (semantic parsing) 또는 분석이다. 계산기 나 통역사의 경우, 행동은 표현이나 프로그램을 평가하는 것입니다. 반면에 컴파일러는 일종의 코드를 생성합니다. 속성 문법을 사용하여 이러한 작업을 정의 할 수도 있습니다.

종류

parsing은 입력 문장에서 단어들의 기능이 문법규칙에 맞는가를 분석하는 것이다. 이를 위해 주어진 문장이 어떻게 출발 심볼로부터 생성되었나를 알아야 한다. 이를 위해서는 top-down and bottom-up parisng 이 존재한다.

문장에서 단어들의 선형적 순서는 서로간에 어떻게 관계되는지를 보여주는 구조로 변형된다. parser 는 문장에서 단어들의 리스트를 "de-linearization" 시켜서 문장의 구조적 의미를 표현하기위한 트리 (derivation tree) 형식으로 변환한다. 대표적인 parsing 기법에는 context free grammar Augmented Transition Networks Conceptual parsing (CD) 등이 있다. 다음 그림과 같이 parsing 에서는 주어-동사, 동사-목적어 등과 같은 중요한 언어학적인 관계를 형성함에 의하여 parser tree 로 표현된다, 단어 분석기(parser)에서는 Semantic analysis 에 대한 기반을 제공한다. 파서 의 임무 는 본질적으로 입력이 문법의 시작 기호에서 도출 될 수 있는지 여부와 방법을 결정하는 것입니다. 기본적으로 두 가지 방법으로 수행 할 수 있습니다.

하향식 구문 분석 -하향식 구문 분석은 주어진 공식 문법 규칙 의 하향식 확장을 사용하여 구문 분석 트리 를 검색하여 입력 스트림의 가장 왼쪽 파생을 찾으려는 시도로 볼 수 있습니다 . 토큰은 왼쪽에서 오른쪽으로 소비됩니다. 포괄적 인 선택은 문법 규칙의 모든 대체 오른쪽을 확장 하여 모호성 을 수용하는 데 사용됩니다 . [9] 상향식 구문 분석 -구문 분석기는 입력으로 시작하여 시작 기호에 다시 쓰려고 시도 할 수 있습니다. 직관적으로 파서는 가장 기본적인 요소를 찾은 다음이를 포함하는 요소 등을 찾습니다. LR 파서 는 상향식 파서 의 예입니다. 이 유형의 구문 분석기에 사용되는 다른 용어는 Shift-Reduce 구문 분석입니다. LL 파서 및 재귀 하강 파서 는 왼쪽 재귀 생산 규칙을 수용 할 수없는 하향식 파서의 예입니다 . 하향식 구문 분석의 간단한 구현은 직간접적인 왼쪽 재귀를 수용 할 수 없으며 모호한 컨텍스트 프리 문법 을 구문 분석하는 동안 지수 시간 및 공간 복잡성을 요구할 수 있다고 생각되었지만, 하향식 구문 분석을 위한보다 정교한 알고리즘은 Frost에 의해 작성되었습니다 모호성 과 왼쪽 재귀 를 수용하는 , Hafiz 및 Callaghan [10] [11]다항식 시간으로 잠재적 지수 지수의 구문 분석 트리의 다항식 크기 ​​표현을 생성합니다. 그들의 알고리즘은 주어진 문맥이없는 문법 과 관련하여 입력의 가장 왼쪽과 가장 오른쪽 파생을 생성 할 수 있습니다 .

파서와 관련하여 중요한 차이점은 파서가 가장 왼쪽 파생 또는 가장 오른쪽 파생을 생성하는지 여부입니다 ( 컨텍스트가없는 문법 참조 ). LL 파서는 가장 왼쪽 파생 을 생성 하고 LR 파서는 가장 오른쪽 파생을 생성합니다 (보통 역순 임). [9]

일부 그래픽 파싱 알고리즘은 비주얼 프로그래밍 언어를 위해 설계되었습니다 . [12] [13] 시각 언어 파서는 때때로 그래프 문법을 기반으로 합니다 . [14]

적응 형 파싱 알고리즘은 "자가 확장" 자연 언어 사용자 인터페이스 를 구성하는 데 사용되었습니다 .

특징

• 프로그램을 compile하는 과정에서 특정 프로그래밍 언어가 제시하는 문법을 잘 지켜서 작성하였는지 compiler가 검사하는 것

ex) XML parser는 XML 문서가 XML 문법에 맞게 작성되었는지 검사

• XML 문서를 읽고 해석하여 태그명, 속성명, 속성값 및 엘리먼트 내용을 분리해 주는 프로그램
• 인터넷에 주어진 정보를 내가 원하는대로 가공하여 서버에서 원하는 때 불러올 수 있도록 하는 것
• 웹 브라우저인 explorer 또한 하나의 응용프로그램으로 XML parser가 parsing(해석)한 결과를 이용해 display 하도록 programming 되었었다
• 어떤 data를 원하는 form으로 만들어 내는 것
• 특정 문서(XML, HTML 등)을 읽어 다른 프로그램이나 서브루틴이 사용할 수 있는 내부의 표현 방식으로 변환해 주는 것

ex) 학교 홈페이지의 공지사항(태그 안의 text 내용이 있는 것)을 읽어와서 그 중 텍스트 내용만 따로 저장하는 등의 다른 프로그램이나 서브루틴이 사용할 수 있는 표현방식으로 변경 (의미를 파악하면서 읽는다- 값이 얼마인지 id 태그의 이름이 무엇인지 등을 파악)

• <>와 같은 태그를 사용자가 입력하면 컴퓨터가 알아볼 수 있도록 바꿔주는 과정
• 컴파일러의 일부로 원시 프로그램의 명령문이나 온라인 명령문, HTML 문서 등에서 Markup Tag 등을 입력으로 받아들여 구문을 해석할 수 있는 단위로 여러부분으로 분할해주는 역할
• Parsing 기법으로 XMl 파싱 기법인 DOM과 SAX / JSON 파싱 기법이 있다

참고자료

• 〈파싱〉, 《위키피디아》
• 킹포도의 코딩, 〈[ https://kingpodo.tistory.com/8]〉, 《티스토리》, 2018-04-29