해석

Parsing
"Parse"는 여기서 리다이렉트 됩니다.다른 용도는 해석(동음이의)을 참조하십시오.

구문 분석, 구문 분석 또는 구문 분석은 자연 언어, 컴퓨터 언어 또는 데이터 구조에서 일련의 기호를 분석하는 과정으로, 형식 문법의 규칙을 준수합니다.구문 분석이라는 용어는 (말의)[1] 부분을 의미하는 라틴어 파스(orationis)에서 유래했습니다.

이 용어는 언어학과 컴퓨터 과학 분야마다 조금씩 다른 의미를 가지고 있습니다.전통적인 문장 해석은 종종 문장이나 단어의 정확한 의미를 이해하는 방법으로 수행되며, 때로는 문장 다이어그램과 같은 장치의 도움을 받아 수행되기도 한다.그것은 보통 주어와 술어와 같은 문법적 구분의 중요성을 강조한다.

컴퓨터 언어학에서 이 용어는 문장 또는 다른 일련의 단어들이 그 구성요소로 들어가는 컴퓨터에 의한 형식적 분석을 참조하기 위해 사용되며, 그 결과 서로에 대한 구문 관계를 보여주는 해석 트리가 생성되며, 의미론 및 다른 정보(p-values)[citation needed]도 포함될 수 있다.구문 분석 알고리즘에 따라 구문 분석 [2]포레스트 또는 구문 분석 트리 목록이 생성될 수 있습니다.

이 용어는 언어 이해를 설명할 때 심리언어학에서도 사용된다.이 맥락에서 파싱은 인간이 문장이나 구문을 (구어 또는 텍스트에서) 문법적 구성 요소, 언어, 구문 관계 [1]등의 관점에서 분석하는 방식을 말한다.이 용어는 어떤 언어적 단서가 화자가 원어민 경로 문장을 해석하는 데 도움이 되는지 논의할 때 특히 일반적이다.

컴퓨터 사이언스 내에서 이 용어는 컴파일러와 인터프리터의 작성을 용이하게 하기 위해 입력 코드의 컴포넌트 부분의 구문 분석을 참조하면서 컴퓨터 언어의 분석에 사용됩니다.이 용어는 분할 또는 분리를 설명하기 위해 사용될 수도 있습니다.

인간의 언어

주요 카테고리: 자연어 해석

종래의 방법

구문 분석의 전통적인 문법적 연습은 때때로 절 분석으로 알려져 있는데, [3]각 부분의 형태, 기능, 구문 관계에 대한 설명과 함께 텍스트를 언어의 구성요소 부분으로 분해하는 것을 포함한다.이것은 상당부분 언어의 활용과 격차에 대한 연구로부터 결정되는데, 이것은 심하게 굴절된 언어에는 상당히 복잡할 수 있다.'man bites dog'와 같은 구문을 해석하는 것은 단수 명사 'man'이 문장의 주어이고, 동사 'bites'는 동사 'to bites'의 현재 시제의 3인칭 단수이고, 단수 명사 'dog'는 문장의 목적어이다.문장의 요소들 사이의 관계를 나타내기 위해 문장 다이어그램과 같은 기법들이 종종 사용된다.

파싱은 이전에는 영어권 전체에서 문법 교육의 중심이었고, 문자의 사용과 이해에 있어 기본적인 것으로 널리 여겨졌다.그러나 이러한 기술의 일반적인 가르침은 [citation needed]더 이상 존재하지 않는다.

계산 방법

주요 기사:구문 해석(컴퓨터 언어학)

일부 기계 번역 및 자연어 처리 시스템에서는 인간의 언어로 쓰여진 텍스트가 컴퓨터 [4]프로그램에 의해 해석됩니다.인간의 문장은 프로그램에 의해 쉽게 해석되지 않는다.인간의 언어 구조에는 상당한 모호성이 존재하기 때문이다.인간의 용도는 잠재적으로 무한한 가능성 범위 사이에서 의미(또는 의미론)를 전달하는 것이지만, 그 중 일부만이 특정 [5]경우에 밀접하게 관련되어 있기 때문이다.그래서 "사람이 개를 물다"와 "개가 사람을 물다"라는 말은 한 가지 세부 사항에서는 분명하지만, 다른 언어에서는 "사람이 개를 물다"로 나타나는데, 만약 그 차이가 정말로 관심사였다면, 이 두 가지 가능성을 구별하기 위해 더 큰 맥락에 의존할 수도 있다.일부 규칙이 [citation needed]지켜지고 있는 것은 분명하지만 비공식적인 행동을 묘사하기 위한 공식적인 규칙을 마련하는 것은 어렵다.

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

대부분의 최신 파서는 적어도 부분적으로 통계적이다. 즉, 이미 주석이 달린 훈련 데이터의 말뭉치에 의존한다(수작업으로 구문 분석).이 접근방식을 통해 시스템은 특정 컨텍스트에서 다양한 구성이 발생하는 빈도에 대한 정보를 수집할 수 있습니다.(머신 러닝 참조).지금까지 사용된 접근법에는 간단한 PCFG(확률론적 문맥 자유 [6]문법), 최대 [7]엔트로피 및 [8]신경망이 포함된다.보다 성공적인 시스템의 대부분은 어휘 통계를 사용한다(즉, 관련된 단어의 정체성 및 언어 부분을 고려한다).그러나 이러한 시스템은 과적합에 취약하며 효과를 [citation needed]발휘하기 위해서는 일종의 스무딩이 필요합니다.

자연어 구문 분석 알고리즘은 프로그래밍 언어를 위해 수동으로 설계된 문법처럼 '나이스' 속성을 가진 문법에 의존할 수 없습니다.앞에서 설명한 바와 같이 일부 문법 형식어는 계산적으로 해석하기가 매우 어렵습니다.일반적으로 원하는 구조가 문맥이 없는 구조가 아니더라도 문법에 대한 어떤 문맥이 없는 근사치가 첫 번째 패스를 수행하기 위해 사용됩니다.문맥이 없는 문법을 사용하는 알고리즘은 CYK 알고리즘의 일부 변형에 의존하는 경우가 많은데, 일반적으로 시간을 절약하기 위해 가능성이 낮은 분석을 제거하는 휴리스틱을 사용합니다.('차트 해석' 참조).그러나 일부 시스템은 예를 들어, 이동 감소 알고리즘의 선형 시간 버전을 사용하여 정확성을 위해 속도를 교환합니다.다소 최근의 개발은 파서가 많은 수의 분석을 제안하고 보다 복잡한 시스템이 최적의 [citation needed]옵션을 선택하는 구문 분석의 재순위화였다.자연어 이해 어플리케이션에서 의미 파서는 텍스트를 의미 [9]표현으로 변환합니다.

심리언어학

심리언어학에서 파싱은 단순히 카테고리에 단어를 할당하는 것뿐만 아니라 문장 내의 각 단어에서 도출된 추론에 의해 도출된 구문 규칙에 따라 문장의 의미를 평가하는 것을 포함한다.이것은 보통 단어를 듣거나 읽을 때 발생합니다.결과적으로, 파싱의 심리언어학적 모델은 필연적으로 증분적이며, 이는 보통 부분 구문 구조의 관점에서 표현되는 문장이 처리될 때 해석을 쌓는다는 것을 의미한다.정원 경로 문장을 해석할 때 초기에 잘못된 구조가 생성된다.

담화 분석

담화 분석은 언어 사용과 기호학적 사건을 분석하는 방법을 조사합니다.설득력 있는 언어는 수사학이라고 할 수 있다.

컴퓨터 언어

파서

"파서"는 여기서 리다이렉트 됩니다.파서라는 이름의 스크립트 언어에 대해서는 파서(프로그래밍 언어)를 참조하십시오.

파서는 입력 데이터(흔히 텍스트)를 받아 데이터 구조(종종 구문 분석 트리, 추상 구문 트리 또는 다른 계층 구조)를 구축하는 소프트웨어 구성 요소로, 올바른 구문을 확인하면서 입력의 구조적 표현을 제공합니다.해석은 다른 스텝의 전후에 실시하거나1개의 스텝으로 조합할 수 있습니다.파서는 종종 입력 문자의 시퀀스에서 토큰을 생성하는 별도의 어휘 분석기가 선행됩니다. 또는 스캐너 없는 파싱에서 이러한 토큰을 결합할 수 있습니다.파서는 수동으로 프로그래밍할 수도 있고 파서 발생기에 의해 자동으로 또는 반자동으로 생성될 수도 있습니다.해석은 형식화된 출력을 생성하는 템플리팅과 보완합니다.이것들은 다른 도메인에 적용될 수 있지만, scanf/printf 쌍, 또는 컴파일러의 입력(프런트 엔드 해석)과 출력(백엔드 코드 생성) 단계 등, 함께 표시되는 경우가 많습니다.

파서에 대한 입력은 종종 일부 컴퓨터 언어로 된 텍스트이지만, 자연 언어로 된 텍스트이거나 덜 구조화된 텍스트 데이터일 수도 있습니다. 이 경우 일반적으로 구문 분석 트리가 생성되는 대신 텍스트의 특정 부분만 추출됩니다.파서는 scanf와 같은 매우 단순한 함수부터 C++ 컴파일러의 프런트 엔드나 웹 브라우저의 HTML 파서 같은 복잡한 프로그램까지 다양합니다.정규 표현의 그룹이 정규 언어를 정의하고 정규 표현 엔진이 자동으로 해당 언어의 파서를 생성하여 패턴 매칭 및 텍스트 추출을 가능하게 하는 단순한 파싱의 중요한 클래스가 정규 표현을 사용하여 이루어진다.다른 컨텍스트에서는 정규 표현이 구문 분석 전에 대신 사용되며, 그 출력은 파서에 의해 사용됩니다.

파서의 사용은 입력에 따라 다릅니다.데이터 언어의 경우 HTML 또는 XML 텍스트 읽기 등 프로그램의 파일 읽기 기능으로 파서가 자주 사용됩니다.이러한 예는 마크업 언어입니다.프로그래밍 언어의 경우 파서는 컴파일러 또는 인터프리터의 컴포넌트이며, 컴퓨터 프로그래밍 언어의 소스 코드를 해석하여 내부 표현의 형태를 만듭니다.파서는 컴파일러 프런트엔드의 주요 단계입니다.프로그래밍 언어는 빠르고 효율적인 파서가 작성될 수 있기 때문에 결정론적 문맥 자유 문법으로 지정되는 경향이 있습니다.컴파일러의 경우 해석 자체는 1패스 또는 여러 패스로 실행할 수 있습니다.원패스 컴파일러와 멀티패스 컴파일러를 참조해 주세요.

원패스 컴파일러의 암묵적인 단점은 주로 수정 기능을 추가하면 극복할 수 있습니다.이 경우, 순방향 패스 중에 코드 재배치를 위한 프로비저닝이 이루어지며, 현재 프로그램 세그먼트가 완료된 것으로 인식되면 수정 기능이 반대로 적용됩니다.이러한 수정 메커니즘이 유용한 예로는 프로그램 세그먼트가 완료될 때까지 GOTO의 타깃을 알 수 없는 순방향 GOTO 문이 있습니다.이 경우 GOTO의 대상이 인정될 때까지 수정 적용이 지연됩니다.반대로 하위 GOTO는 위치가 이미 알려져 있기 때문에 수정이 필요하지 않습니다.

문맥이 없는 문법은 언어의 모든 요구 사항을 표현할 수 있는 범위 내에서 제한됩니다.비공식적으로, 그 이유는 그러한 언어의 기억력이 제한적이기 때문이다.문법은 임의로 긴 입력에 대한 구문 존재를 기억할 수 없습니다. 예를 들어 이름을 선언해야 참조할 수 있는 언어에 필요합니다.그러나 이 제약을 표현할 수 있는 보다 강력한 문법은 효율적으로 구문 분석할 수 없습니다.따라서 원하는 언어 구문(즉, 일부 비활성 구문)을 받아들이는 문맥 없는 문법에 대해 완화된 파서를 작성하는 것이 일반적인 전략입니다.나중에 의미 분석(문맥 분석) 단계에서 불필요한 구문들을 걸러낼 수 있습니다.

예를 들어 Python에서는 구문적으로 유효한 코드가 다음과 같습니다.

x = 1 인쇄물(x)

단, 다음 코드는 문맥이 없는 문법에 관해서는 구문적으로 유효하며 이전과 동일한 구조의 구문 트리를 생성하지만 사용하기 전에 변수를 초기화해야 하는 의미 규칙을 위반합니다.

x = 1 인쇄물(y)

프로세스의 개요

Flow of data in a typical parser

다음 예시는 어휘와 구문이라는 두 가지 수준의 문법을 사용하여 컴퓨터 언어를 구문 분석하는 일반적인 경우를 보여 줍니다.

첫 번째 단계는 토큰 생성 또는 어휘 분석으로, 입력 문자 스트림이 정규 표현의 문법에 의해 정의된 의미 있는 기호로 분할됩니다.예를 들어, 계산기 프로그램은 다음과 같은 입력을 조사합니다.12 * (3 + 4)^2토큰으로 분할합니다.12,*,(,3,+,4,),^,2각각 산술식의 맥락에서 의미 있는 기호입니다.그 렉서에는 그 글자를 알려주는 규칙이 포함되어 있을 것이다.*,+,^,(그리고.)"와 같은 의미 없는 토큰의 시작을 알립니다.12*" 또는(3"는 생성되지 않습니다.

다음 단계는 구문 분석 또는 구문 분석으로, 토큰이 허용 가능한 식을 형성하는지 확인합니다.이것은 보통 문맥이 없는 문법에 따라 이루어집니다.문맥이 없는 문법은 식을 구성하는 컴포넌트와 그것들이 표시되는 순서를 재귀적으로 정의합니다.그러나 프로그래밍 언어를 정의하는 모든 규칙이 문맥이 없는 문법만으로 표현될 수 있는 것은 아닙니다. 예를 들어 유형 유효성 및 식별자의 적절한 선언입니다.이러한 규칙은 속성 문법으로 정식으로 표현될 수 있습니다.

마지막 단계는 의미 해석 또는 분석으로, 방금 검증된 표현의 의미를 파악하여 적절한 [10]조치를 취합니다.계산기 또는 인터프리터의 경우, 동작은 식이나 프로그램을 평가하는 것입니다.반면 컴파일러는 어떤 종류의 코드를 생성합니다.속성 문법을 사용하여 이러한 작업을 정의할 수도 있습니다.

파서의 종류

파서의 작업은 기본적으로 입력이 문법의 시작 기호에서 도출될 수 있는지 여부와 방법을 결정하는 것입니다.이는 기본적으로 다음 두 가지 방법으로 수행할 수 있습니다.

  • 하향식 구문 분석 - 하향식 구문 분석은 지정된 형식 문법 규칙의 하향식 확장을 사용하여 구문 분석 트리를 검색하여 입력 스트림의 가장 왼쪽 파생 항목을 찾으려는 시도라고 볼 수 있습니다.토큰은 왼쪽에서 오른쪽으로 소비됩니다.포괄적 선택은 문법 [11]규칙의 모든 대안적인 오른쪽을 확장함으로써 모호함을 수용하기 위해 사용됩니다.이것은 원시 수프 접근법으로 알려져 있다.문장 도표 작성과 매우 유사하게, 원시 수프는 [12]문장의 구성 요소를 분해합니다.
  • Bottom-up parsing - 파서는 입력으로 시작하여 시작 기호로 다시 쓰기를 시도할 수 있습니다.직관적으로 파서는 가장 기본적인 요소를 찾은 다음 이를 포함하는 요소를 찾는 등의 작업을 시도합니다.LR 파서는 상향식 파서의 예입니다.이런 유형의 파서에 사용되는 또 다른 용어는 Shift-Reduce 구문 분석입니다.

LL 파서 및 recursive-descent 파서는 왼쪽 재귀 생성 규칙을 수용할 수 없는 하향식 파서의 예입니다.비록 그것은 하향식 구문 분석의 간단한 구현하고 모호한 문맥 자유 grammars을 구문 분석하기 지수 시간과 공간 복잡도 필요할 수 있고 간접적인 left-recursion을 수용할 수 없 여겨져 왔다 하향식 구문 분석을 위한 보다 편리한 알고리즘, 프로스트 하피즈, Callaghan[13][14]는 acc에 의해 창조되었다는 것.ommodate 모호성 및 다항식 시간에서의 왼쪽 재귀 및 잠재적으로 지수적인 수의 구문 분석 트리의 다항식 크기 표현을 생성합니다.이들의 알고리즘은 주어진 문맥이 없는 문법에 관해 입력의 왼쪽 끝과 오른쪽 끝의 파생어를 모두 생성할 수 있다.

파서에 관한 중요한 차이는 파서가 최좌파 파생 또는 최우파 파생 중 어느 쪽을 생성하느냐이다(문맥 자유 문법 참조).LL 파서는 최좌측 유도체를 생성하고 LR 파서는 최우측 유도체를 생성합니다(일반적으로 역방향).[11]

일부 그래픽 구문 분석 알고리즘은 시각적 프로그래밍 [15][16]언어용으로 설계되었습니다.시각 언어의 파서는 그래프 [17]문법에 기반할 수 있습니다.

적응 구문 분석 알고리즘은 "자기 확장" 자연 언어 사용자 인터페이스를 [18]구성하기 위해 사용되었습니다.

실행

가장 단순한 파서 API는 입력 파일 전체를 읽고 중간 계산을 수행한 다음 출력 파일 전체를 씁니다(메모리 내 멀티패스 컴파일러 등).

전체 입력 파일 또는 전체 출력 파일을 저장할 메모리가 부족하면 이러한 간단한 파서는 작동하지 않습니다.또, 현실에서 끝없는 데이터 스트림에도 대응할 수 없습니다.

이러한 데이터를 해석하기 위한 대체 API 접근법:

  • 파서가 입력 스트림(Expat 등)에서 관련된 토큰을 검출하면 즉시 등록된 핸들러(콜백)를 호출하는 푸시 파서
  • 파서를 당기다
  • 증분 파서(예: 증분 차트 파서)는 사용자가 파일 텍스트를 편집하기 때문에 파일 전체를 완전히 다시 작성할 필요가 없습니다.
  • 액티브 파서와 패시브[19][20] 파서

파서 개발 소프트웨어

다음 항목도 참조하십시오.파서 생성기 비교

잘 알려진 파서 개발 도구에는 다음과 같은 것이 있습니다.

미리 보다

2개 미만의 토큰 검색으로 구문 분석할 수 없는 C 프로그램입니다.Top: C 문법 [21]발췌.맨 아래: 파서가 토큰을 요약했습니다.int v;main(){" Stmt를 도출할 규칙을 선택합니다.첫 번째 미리 보기 토큰만 보는 중"vStmt가 어느 쪽을 선택할지 결정할 수 없습니다.두 번째 토큰을 훔쳐봐야 합니다.

Lookahead는 파서가 사용해야 하는 규칙을 결정하는 데 사용할 수 있는 최대 수신 토큰 수를 설정합니다.LL, LR 및 LALR 파서와 특히 관련이 있으며, LALR (1)과 같은 알고리즘 이름에 룩어헤드(lookahead)를 붙이는 것으로 명시적으로 나타납니다.

파서의 주요 타깃인 대부분의 프로그래밍 언어는 제한된 룩어헤드(일반적으로 1개)를 가진 파서가 파서를 해석할 수 있도록 주의 깊게 정의되어 있습니다.이는 룩어헤드(look어헤드)가 제한된 파서가 종종 더 효율적이기 때문입니다.이러한 추세에 대한 한 가지 중요한[citation needed] 변화는 1990년 Terence Parr가 박사 학위 논문의 ANTLR을 만들면서 일어났다. 여기서 k는 고정값이다.

LR 파서는 일반적으로 각 토큰을 확인한 후 몇 가지 작업만 수행합니다.예를 들어 shift(나중에 줄이기 위해 이 토큰을 스택에 추가), reduced(스택에서 토큰을 팝하여 구문 구조를 형성), end, error(적용되지 않은 규칙) 또는 conflict(시프트 또는 축소 여부를 알 수 없음)입니다.

Lookahead에는 두 가지 [clarification needed]장점이 있습니다.

  • 그러면 파서가 충돌 시 올바른 조치를 취할 수 있습니다.예를 들어, else 구의 경우 if 문을 해석합니다.
  • 중복 상태를 많이 제거하고 추가 스택에 대한 부담을 덜어줍니다.C 언어 비룩어헤드 파서는 약 10,000개의 상태를 가집니다.미리 보기 파서는 약 300개의 상태를 가집니다.

예: 식 1 + 2 * 3의[dubious – discuss] 해석

표현식 구문 분석 규칙(문법이라고 함)의 집합은 다음과 같습니다.
규칙 1: E → E + E 표현은 두 표현의 합계입니다.
규칙 2: E → E * E 표현은 두 표현의 산물입니다.
규칙 3: E → 번호 식은 단순한 숫자입니다.
규칙 4: +는 *보다 우선순위가 낮습니다.

대부분의 프로그래밍 언어(APL이나 Smalltalk 등 일부 언어 제외)와 대수식은 덧셈보다 곱셈에 더 높은 우선순위를 부여합니다. 이 경우 위의 예제의 올바른 해석은 1 + (2 * 3)입니다.위의 Rule4는 시멘틱 규칙 4는 의미 규칙입니다.이것을 구문에 짜넣기 위해서 문법을 고쳐 쓸 수 있습니다.단, 이러한 모든 규칙을 구문으로 변환할 수 있는 것은 아닙니다.

단순 비전망 파서 작업

초기 입력 = [1, +, 2, *, 3]

  1. (규칙3을 예상하고) 입력에서 스택으로 "1"을 이동합니다.입력 = [+, 2, *, 3] 스택 = [1]
  2. 규칙 3에 따라 식 "1"을 식 "E"로 줄입니다.스택 = [E]
  3. (규칙 1을 예상하고) 입력에서 스택으로 "+"를 이동합니다.입력 = [2, *, 3] 스택 = [E, +]
  4. (규칙3을 예상하고) 입력에서 스택으로 "2"를 이동합니다.입력 = [*, 3] 스택 = [E, +, 2]
  5. 스택 요소 "2"를 규칙 3에 따라 식 "E"로 줄입니다.스택 = [E, +, E]
  6. 스택 항목 [E, +, E]와 새로운 입력 "E"를 규칙 1에 따라 "E"로 줄입니다.스택 = [E]
  7. (규칙 2를 예상하고) 입력에서 스택으로 "*"를 이동합니다.입력 = [3] 스택 = [E,*]
  8. (규칙 3을 예상하고) 입력에서 스택으로 "3"을 이동합니다.입력 = [] (빈) 스택 = [E, *, 3]
  9. 스택 요소 "3"을 규칙 3에 따라 식 "E"로 줄입니다.스택 = [E, *, E]
  10. 규칙 2에 따라 스택 항목 [E, *, E] 및 새로운 입력 "E"를 "E"로 줄입니다.스택 = [E]

구문 분석 트리와 그 결과 코드가 언어 의미론에 따라 올바르지 않습니다.

사전 검색 없이 올바르게 구문 분석하려면 다음 세 가지 솔루션이 있습니다.

  • 사용자는 식을 괄호로 묶어야 합니다.이것은 종종 실행 가능한 해결책이 아니다.
  • 규칙을 위반하거나 완료되지 않을 때마다 역추적 및 재시도하려면 파서가 더 많은 논리를 가지고 있어야 합니다.LL 파서에서도 같은 방법이 사용됩니다.
  • 또는 파서 또는 문법은 어떤 규칙을 먼저 축소해야 하는지 확실히 알 수 있을 때만 축소를 지연시키고 축소하기 위한 추가 논리를 필요로 합니다.이 메서드는 LR 파서에서 사용됩니다.이렇게 하면 식을 올바르게 해석할 수 있지만 상태가 더 많아지고 스택 깊이가 증가합니다.
사전 구문 분석기 작업[clarification needed]
  1. 규칙 3을 예상하고 입력 1의 스택으로 1을 이동합니다.바로 줄어들지는 않습니다.
  2. 스택 항목 1을 규칙 3에 따라 입력 +에 대한 단순한 식으로 줄입니다.예측값은 +이므로 E+로 향하는 경로이므로 스택을 E로 줄일 수 있습니다.
  3. +를 입력 +의 스택으로 이동하고 규칙 1을 예측합니다.
  4. 규칙 3을 예상하고 입력 2의 스택으로 2를 이동합니다.
  5. 스택 항목 2를 규칙 3에 따라 입력 *의 식(Expression on input *)으로 줄입니다.lookahead *는 앞에 E만 예상합니다.
  6. 스택은 E+E로 입력은 * 입니다.이제 규칙 2에 따라 전환할지 규칙 1에 따라 축소할지 두 가지 선택지가 있습니다.규칙 4에 따르면 *는 +보다 우선도가 높기 때문에 규칙 2를 예상하고 *를 스택으로 이동합니다.
  7. 규칙 3을 예상하고 3을 입력 3의 스택으로 전환합니다.
  8. 규칙 3에 따라 입력의 끝을 확인한 후 스택 항목 3을 식으로 줄입니다.
  9. 규칙 2에 따라 스택 항목 E * E를 E로 줄입니다.
  10. 스택 항목 E + E를 규칙 1에 따라 E로 줄입니다.

생성된 구문 분석 트리는 정확하고 단순히 비예측 구문 분석기보다 효율적입니다[clarify][citation needed].이것은 LALR 파서에서의 전략입니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b "Parse". dictionary.reference.com. Retrieved 27 November 2010.
  2. ^ Masaru Tomita (6 December 2012). Generalized LR Parsing. Springer Science & Business Media. ISBN 978-1-4615-4034-2.
  3. ^ "Grammar and Composition".
  4. ^ Christopher D.. Manning; Christopher D. Manning; Hinrich Schütze (1999). Foundations of Statistical Natural Language Processing. MIT Press. ISBN 978-0-262-13360-9.
  5. ^ Jurafsky, Daniel (1996). "A Probabilistic Model of Lexical and Syntactic Access and Disambiguation". Cognitive Science. 20 (2): 137–194. CiteSeerX 10.1.1.150.5711. doi:10.1207/s15516709cog2002_1.
  6. ^ 클라인, 댄, 크리스토퍼 D.매니닝."정확한 비플렉서화 구문 분석"제41회 컴퓨터 언어학회 연차총회 - 제1권.컴퓨터 언어학 협회, 2003.
  7. ^ 차니악, 유진"최대의 엔트로피에서 영감을 얻은 파서" 컴퓨터 언어학 협회 제1회 북미 지부 회의 진행.컴퓨터 언어학 협회, 2000.
  8. ^ 첸, 단치, 크리스토퍼 매닝입니다"뉴럴 네트워크를 사용한 빠르고 정확한 의존성 분석기"자연언어처리(EMNLP)의 경험적 방법에 관한 2014년 회의의 진행.2014.
  9. ^ Jia, Robin; Liang, Percy (2016-06-11). "Data Recombination for Neural Semantic Parsing". arXiv:1606.03622 [cs.CL].
  10. ^ 베란트, 조나단, 그리고 퍼시 량."의미적 해석, 의역법 사용"컴퓨터 언어학 협회 제52회 연차총회(제1권: 장문의 논문).2014.
  11. ^ a b Aho, A.V., Sethi, R. 및 Ulman, J.D.(1986) "컴파일러: 원리, 기술, 도구." 애디슨 웨슬리 롱맨 출판사 보스턴, 매사추세츠, 미국
  12. ^ Sikkel, Klaas, 1954- (1997). Parsing schemata : a framework for specification and analysis of parsing algorithms. Berlin: Springer. ISBN 9783642605413. OCLC 606012644.{{cite book}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  13. ^ Frost, R., Hafiz, R. 및 Callaghan, P. (2007) "모호한 왼쪽 반복 문법을 위한 모듈러형 효율적인 하향식 구문 분석 ." 제10회 파싱 테크놀로지(IWPT), ACL-SIGPARSE, 2007년 6월 109페이지, 프라하.
  14. ^ Frost, R., Hafiz, R. 및 Callaghan, P. (2008) "모호한 좌회귀 문법을 위한 파서 조합자." 제10회 선언적 언어의 실용적 측면에 관한 국제 심포지엄(PADL), ACM-SIGPLAN, 4902/2008, 181 페이지:
  15. ^ Rekers, Jan, and Andy Schurr.「그래프 문법에 의한 비주얼 언어의 정의와 해석」.Journal of Visual Languages & Computing （ 1997 ） : 27 - 55 。
  16. ^ Rekers, Jan 및 A.슈어"그래픽 구문 분석에 대한 그래프 문법 접근법"비주얼 언어, 프로시딩스, 제11회 IEEE 국제 심포지엄 on.IEEE, 1995.
  17. ^ 장, 다첸, 강장, 지안농조."시각 언어 지정에 대한 문맥 의존 그래프 문법 형식주의"Computer Journal 44.3 (2001)
  18. ^ Jill Fain Lehman (6 December 2012). Adaptive Parsing: Self-Extending Natural Language Interfaces. Springer Science & Business Media. ISBN 978-1-4615-3622-2.
  19. ^ 패트릭 블랙번과 크리스티나 스트리그니츠입니다"프롤로그의 자연어 처리 기술"
  20. ^ Song-Chun Zhu. "고전 구문 분석 알고리즘"
  21. ^ (부록 A.13 "문법", 페이지 193 ff)에서 인용한 내용

추가 정보

외부 링크

무료 사전인 Wiktionary에서 구문 분석 또는 구문 분석을 검색합니다.