구문 분석: 컴파일러 하향식 및 상향식 구문 분석 유형

컴파일러 설계 프로세스에서 구문 분석은 어휘 분석 단계 다음에 옵니다. 이를 파스 트리 또는 구문 트리라고도 합니다. 파스 트리는 언어의 사전 정의된 문법을 사용하여 개발됩니다. 구문 분석기는 또한 주어진 프로그램이 문맥 없는 문법에 의해 암시된 규칙을 충족하는지 확인합니다. 충족하는 경우 파서는 해당 소스 프로그램의 파스 트리를 만듭니다. 그렇지 않으면 오류 메시지를 표시합니다.

구문 분석기가 필요한 이유는 무엇입니까?

• 코드가 문법적으로 유효한지 확인하세요.
• 구문 분석기는 코드에 규칙을 적용하는 데 도움이 됩니다.
• 각 개시 중괄호에 해당 마감 잔액이 있는지 확인하는 데 도움이 됩니다.
• 각 선언에는 유형이 있으며 해당 유형이 존재해야 합니다.

중요한 구문 분석기 용어

구문 분석 프로세스에 사용되는 중요한 용어:

• 문장: 문장은 일부 알파벳에 대한 문자 그룹입니다.

• 어휘소: 어휘소는 언어의 가장 낮은 수준의 구문 단위입니다(예: total, start).

• 토큰 : 토큰은 어휘소의 범주일 뿐입니다.

• 키워드 및 예약어 – 구문 구문의 고정 부분으로 사용되는 식별자입니다. 변수명이나 식별자로 사용할 수 없는 예약어입니다.

• 소음 단어 – 문장의 가독성을 높이기 위해 문장에 삽입되는 의미 없는 단어는 선택 사항입니다.

• 코멘트 – 문서화에서 매우 중요한 부분입니다. 주로 /* */ 또는//공백(공백)으로 표시됩니다.

• 구분자 – 일부 구문 단위의 시작 또는 끝을 표시하는 구문 요소입니다. 명령문이나 표현식과 마찬가지로 "begin"..."end" 또는 {}입니다.

• 문자 세트 – ASCII, 유니코드

• 식별자 – 문장의 가독성을 낮추는 데 도움이 되는 길이 제한입니다.

• Opera토르 기호 – + 및 –는 두 가지 기본적인 산술 연산을 수행합니다.
• 언어의 구문적 요소

왜 파싱이 필요한가요?

또한 구문 분석은 입력 문자열의 형식이 올바른지 확인하고 그렇지 않은 경우 거부합니다.

컴파일러 설계에서 파서가 수행하는 중요한 작업은 다음과 같습니다.

• 모든 유형의 구문 오류를 감지하는 데 도움이 됩니다.
• 에러가 발생한 위치 찾기
• 오류에 대한 명확하고 정확한 설명입니다.
• 계속해서 코드에서 추가 오류를 찾으려면 오류를 복구하세요.
• "올바른" 프로그램의 컴파일에 영향을 주어서는 안 됩니다.
• 구문 분석에서는 구문 오류를 보고하여 잘못된 텍스트를 거부해야 합니다.

구문 분석 기술

구문 분석 기술은 두 가지 그룹으로 나뉩니다.

• 하향식 구문 분석,
• 상향식 구문 분석

하향식 구문 분석

하향식 구문 분석에서 구문 분석 트리의 구성은 루트에서 시작한 다음 리프를 향해 진행됩니다.

하향식 구문 분석에는 두 가지 유형이 있습니다.

1. 예측 구문 분석:

예측 구문 분석은 특정 입력 문자열을 대체하기 위해 어떤 프로덕션을 사용해야 하는지 예측할 수 있습니다. 예측 파서는 다음 입력 기호를 가리키는 미리보기 지점을 사용합니다. 역추적은 이 구문 분석 기술에서 문제가 되지 않습니다. LL(1) 파서라고도 합니다.

2. 재귀 하강 구문 분석:

이 구문 분석 기술은 입력을 재귀적으로 구문 분석하여 구문 트리를 만듭니다. 이는 문법의 각 비터미널에 대해 하나씩 여러 개의 작은 함수로 구성됩니다.

상향식 구문 분석

컴파일러 설계에서 하향식 파싱에서 파스 트리의 구성은 leave에서 시작하여 루트로 처리됩니다. 이를 shift-reduce 파싱이라고도 합니다. 컴파일러 설계에서 이러한 유형의 파싱은 몇 가지를 사용하여 만들어집니다. 소프트웨어 도구.

오류 – 복구 방법

시스템 소프트웨어에서 구문 분석 시 발생하는 일반적인 오류

• 어휘: 잘못 입력된 식별자의 이름
• 구문론적: 불균형한 괄호 또는 누락된 세미콜론
• 의미론적: 호환되지 않는 값 할당
• 논리: 무한 루프 및 도달할 수 없는 코드

파서는 프로그램에서 발견된 모든 오류를 감지하고 보고할 수 있어야 합니다. 따라서 오류가 발생할 때마다 파서는 이를 처리하고 나머지 입력을 파싱할 수 있어야 합니다. 프로그램은 다양한 컴파일 프로세스 단계에서 다음과 같은 유형의 오류를 가질 수 있습니다. 파서에서 구현할 수 있는 다섯 가지 일반적인 오류 복구 방법이 있습니다.

명령문 모드 복구

• 파서에 오류가 발생한 경우 수정 조치를 취하는 데 도움이 됩니다. 이를 통해 나머지 입력 및 상태를 미리 구문 분석할 수 있습니다.
• 예를 들어 누락된 세미콜론을 추가하는 것은 명령문 모드 복구 방법에서 제공됩니다. 그러나 구문 분석 디자이너는 잘못된 수정으로 인해 무한 루프가 발생할 수 있으므로 이러한 변경을 수행하는 동안 주의해야 합니다.

패닉 모드 복구

• 파서가 오류를 발견하는 경우, 이 모드는 나머지 문장을 무시하고 세미콜론과 같이 구분 기호에 대한 오류 입력을 처리하지 않습니다. 이는 간단한 오류 복구 방법입니다.
• 이 유형의 복구 방법에서 파서는 지정된 단일 동기화 토큰 그룹이 발견될 때까지 입력 심볼을 하나씩 거부합니다. 동기화 토큰은 일반적으로 또는와 같은 구분 기호를 사용합니다.

구문 수준 복구

• 컴파일러는 토큰을 삽입하거나 삭제하여 프로그램을 수정합니다. 이를 통해 원래 위치에서 구문 분석을 진행할 수 있습니다. 나머지 입력에 대해 수정을 수행합니다. 나머지 입력의 접두사를 일부 문자열로 대체할 수 있으며 이는 파서가 프로세스를 계속하는 데 도움이 됩니다.

오류 생산

• 오류 생성 복구는 오류 구조를 생성하는 언어의 문법을 확장합니다. 그런 다음 파서는 해당 구조에 대한 오류 진단을 수행합니다.

전역 교정

• 컴파일러는 잘못된 입력 문자열을 처리하는 동안 가능한 한 적은 수의 변경을 해야 합니다. 잘못된 입력 문자열 a와 문법 c가 주어지면 알고리즘은 관련 문자열 b에 대한 파스 트리를 검색합니다. 토큰의 일부 삽입, 삭제 및 수정과 같이 an을 b로 변환하는 데 필요한 것은 가능한 한 적습니다.

문법

문법은 언어를 설명하는 구조적 규칙의 집합입니다. 문법은 모든 문장에 구조를 할당합니다. 이 용어는 또한 이러한 규칙에 대한 연구를 의미하며 이 파일에는 형태론, 음운론 및 구문이 포함됩니다. 이는 다음 구문의 많은 부분을 설명할 수 있습니다. 프로그래밍 언어.

형식 문법의 규칙

• 비터미널 기호는 최소한 하나의 제품 왼쪽에 나타나야 합니다.
• 목표 기호는 어떠한 프로덕션의 ::= 오른쪽에 표시되어서는 안 됩니다.
• LHS가 RHS에 나타나면 규칙은 재귀적입니다.

표기법

표기 규칙 기호는 요소를 대괄호로 묶어서 표시할 수 있습니다. 이는 요소의 인스턴스의 임의의 시퀀스이며 요소를 중괄호로 묶고 별표 기호 { … }*를 붙여서 표시할 수 있습니다.

단일 규칙 내에서 기호를 사용할 수 있는 대안의 선택이다. 필요한 경우 괄호([,])로 묶을 수 있습니다.

두 가지 유형의 표기 규칙 영역 터미널 및 비 터미널

1.터미널:

• a, b, c와 같은 알파벳 소문자
• Opera+,-, * 등과 같은 토르 기호
• 괄호, 해시, 쉼표 등의 구두점 기호
• 0, 1, …, 9자리
• id 또는 if와 같은 굵은 문자열(단일 터미널 기호를 나타내는 모든 것)

2.비단말기:

• A, B, C와 같은 대문자
• 소문자 이탤릭체 이름: 표현식 또는 일부

문맥에 구애받지 않는 문법

CFG는 해당 유형의 생성이 하나 이상 있는 왼쪽 재귀 문법입니다. 문맥 자유 문법의 규칙은 주로 재귀적입니다. 구문 분석기는 특정 프로그램이 Context-free 문법의 모든 규칙을 만족하는지 여부를 확인합니다. 충족하는 경우 이러한 규칙 구문 분석기는 해당 프로그램에 대한 구문 분석 트리를 생성할 수 있습니다.

expression -> expression -+ term
expression -> expression – term 
expression-> term
term  -> term * factor
term -> expression/ factor
term  -> factor factor
factor ->  ( expression )
factor -> id

문법 파생

문법 파생은 시작 기호를 문자열로 변환하는 일련의 문법 규칙입니다. 파생은 문자열이 문법 언어에 속함을 증명합니다.

가장 왼쪽 파생

입력의 문장형을 스캔하고 왼쪽에서 오른쪽 순서로 바꾸는 것을 가장 왼쪽 파생이라고 합니다. 가장 왼쪽 파생에 의해 파생된 문장 형식을 왼쪽 문장 형식이라고 합니다.

가장 오른쪽 파생

가장 오른쪽 파생 스캔을 수행하고 입력을 오른쪽에서 왼쪽 순서로 생산 규칙으로 바꿉니다. 이는 가장 오른쪽 파생으로 알려져 있습니다. 가장 오른쪽 파생에서 파생된 문장 형식을 오른쪽 문장 형식이라고 합니다.

구문 대 어휘 분석기

구문 분석기	어휘 분석기
구문 분석기는 주로 언어의 재귀적 구성을 다룹니다.	어휘 분석기는 구문 분석기의 작업을 쉽게 해줍니다.
구문 분석기는 소스 프로그램의 토큰에 대해 작동하여 프로그래밍 언어의 의미 있는 구조를 인식합니다.	어휘 분석기는 소스 프로그램의 토큰을 인식합니다.
이는 어휘 분석기로부터 토큰 형태로 입력을 받습니다.	에서 제공하는 토큰의 유효성을 담당합니다. 구문 분석기

구문 분석기 사용의 단점

• 토큰이 유효한지 여부는 결코 결정되지 않습니다.
• 토큰 유형에서 수행된 작업이 유효한지 여부를 판별하는 데 도움이 됩니다.
• 토큰이 사용되기 전에 선언 및 초기화되도록 결정할 수 없습니다.

제품 개요

• 구문 분석은 어휘 분석 이후에 나오는 컴파일러 설계 프로세스의 두 번째 단계입니다.
• 구문 분석기는 코드에 규칙을 적용하는 데 도움이 됩니다.
• 문장, 어휘소, 토큰, 키워드 및 예약어, 의미 없는 단어, 주석, 구분 기호, 문자 세트, 식별자는 컴파일러 구성의 구문 분석에 사용되는 중요한 용어입니다.
• 구문 분석은 입력 문자열이 올바른 형식인지 확인하고 그렇지 않은 경우 거부합니다.
• 구문 분석 기술은 하향식 구문 분석, 상향식 구문 분석의 두 가지 그룹으로 나뉩니다.
• 어휘, 구문, 의미 및 논리는 구문 분석 방법 중에 발생하는 몇 가지 일반적인 오류입니다.
• 문법은 언어를 설명하는 구조적 규칙의 집합입니다.
• 표기 규칙 기호는 요소를 대괄호로 묶어 표시할 수 있습니다.
• CFG는 다음 유형의 생성이 하나 이상 있는 왼쪽 재귀 문법입니다.
• 문법 파생은 시작 기호를 문자열로 변환하는 일련의 문법 규칙입니다.
• 구문 분석기는 주로 언어의 재귀 구성을 다루는 반면 어휘 분석기는 구문 분석기의 작업을 다음과 같이 쉽게 해줍니다. DBMS
• 구문 분석기 방법의 단점은 토큰이 유효한지 여부를 결코 판단하지 못한다는 것입니다.