이 기사에서는 하이 레벨 입력 프로그램이 일련의 토큰으로 변환되는 컴파일러 디자인의 첫 번째 단계에 대해 설명합니다. 이 단계를 컴파일러 디자인에서 어휘 분석이라고 합니다.
목차:
- 어휘 분석을위한 정의
- 어휘 분석의 예
- 어휘 분석기의 아키텍처
- 정규 표현식
- 유한 오토마타
- 정규 표현식과 유한 오토마타 사이의 관계
- 가장 긴 일치 규칙
- 어휘 오류
- 오류 복구 체계
- 어휘 분석기의 필요성
- 어휘 분석기의 필요성
어휘 분석은 입력으로 사용되는 소스 프로그램에서 일련의 문자를 토큰 시퀀스로 변환하는 프로세스입니다.
렉스는 어휘 분석기를 생성하는 프로그램입니다.
어휘 분석기/렉서/스캐너는 어휘 분석을 수행하는 프로그램입니다.
어휘 분석기의 역할 수반;
- 소스 프로그램에서 입력 문자 읽기.
- 소스 프로그램과 오류 메시지의 상관 관계.
- 소스 프로그램의 공백과 주석을 스트라이핑합니다.
- 소스 프로그램에 있는 경우 확장 매크로.
- 식별된 토큰을 기호 테이블에 입력합니다.
어휘는 토큰의 인스턴스,즉 토큰의 매칭 패턴에 따라 소스 프로그램에 포함된 문자 시퀀스이다.
표현식 주어진 예;
씨=+비*5
어휘와 토큰은 다음과 같습니다;
| 어휘 | 토큰 |
|---|---|
| 식별자 | |
| = | 할당 기호 |
| 식별자 | |
| + | +(추가 기호) |
| 식별자 | |
| * | *(곱셈 기호) |
| 5 | 5(번호) |
어휘 분석기에 의해 생성 된 토큰의 시퀀스는 파서의 구문을 분석 할 수 있습니다. 프로그래밍 언어.
토큰은 어휘에 의해 주어진 유효한 문자 시퀀스이며 프로그래밍 언어의 문법에서 단위로 처리됩니다.
프로그래밍 언어에는 다음이 포함될 수 있습니다;
- 키워드
- 연산자
- 구두점 기호
- 상수
- 식별자
- 숫자
패턴은 토큰에서 사용하는 일련의 문자(어휘)와 일치하는 규칙입니다. 정규 표현식 또는 문법 규칙에 의해 정의 될 수 있습니다.
어휘 분석의 예
코드
#include<iostream>// exampleint main(){ int a, b; a = 7; return 0;}토큰
| 어휘 | 토큰 |
|---|---|
| 키워드 | |
| 메인 | 키워드 |
| ( | 운영자 |
| ) | 운영자 |
| { | 운영자 |
| 키워드 | |
| 식별자 | |
| , | 운영자 |
| 비 | 식별자 |
| ; | 운영자 |
| 식별자 | |
| = | 할당 기호 |
| 10 | 10(번호) |
| ; | 운영자 |
| 반환 | 키워드 |
| 0 | 0(번호) |
| ; | 연산자 |
| } | 운영자 |
비 토큰
| 유형 | 토큰 |
|---|---|
| 전처리기 지시문 | #include<iostream> |
| 주석 | //예 |
어휘 분석 과정은 두 단계로 구성됩니다.
- 스캔-여기에는 입력 문자를 읽고 공백 및 주석을 제거하는 작업이 포함됩니다.
- 토큰화-이것은 출력으로서 토큰의 생산이다.
어휘 분석기의 아키텍처
어휘 분석기의 주요 임무는 전체 소스 프로그램을 스캔하고 토큰을 하나씩 식별하는 것입니다.
스캐너는 파서가 요청할 때 토큰을 생성하도록 구현됩니다.
단계:
- “다음 토큰 가져 오기”는 파서에서 어휘 분석기로 전송됩니다.
- 어휘 분석기는”다음 토큰”이 있을 때까지 입력을 스캔합니다.
- 토큰이 파서로 반환됩니다.
정규 표현식
우리는 유한 한 기호 집합에 대한 패턴을 정의하여 유한 언어를 표현하기 위해 정규 표현식을 사용합니다.
정규 표현식에 의해 정의 된 문법은 일반 문법으로 알려져 있으며 일반 문법에 의해 정의 된 언어는 일반 언어로 알려져 있습니다.
정규 표현식을 동등한 형식으로 조작하는 데 사용되는 정규 표현식에 의해 준수되는 대수 규칙이 있습니다.
작업.2013 년 11 월 15 일(토)~2013 년 12 월 15 일(일)~2013 년 12 월 15 일(일)~2013 년 12 월 15 일(일)~2013 년 12 월 15 일(일)~2013 년 12 월 15 일(일)~2013 년 12 월 15 일(일)~2013 년 12 월 15 일(일)~2013 년 12 월 15 일(일)~2013 년 12 월 15 일(일)~2013 년 12 월 15 일(일)~2013 년 12 월 15 일(일)~2013 년 6590>
표기법.예를 들어,정규 표현식은 다음과 같이 표현 될 수 있습니다.정규 표현식은 다음과 같습니다.이 표현식에는 두 개의 정규 표현식이 있습니다.이 표현식에는 다음과 같은 표현식이 포함되어 있습니다.
*’연결.’및/(파이프)는 연관되어 있습니다.
클린 클로저*가 우선 순위가 가장 높습니다.
연결(.)우선 순위를 따릅니다.
(파이프|/우선 순위가 가장 낮습니다.
정규 표현식에서 언어의 유효한 토큰을 나타냅니다.
X 은 정기적인 표현,따라서;
- x*나타내거나 하나 이상의 발생 x.
- x+을 나타내는 하나 이상의 발생 x,ie{x,xx,xxx}
- x? 2795>
- 영어의 모든 소문자 알파벳을 나타냅니다.
- 은 영어의 모든 대문자 알파벳을 나타냅니다.
- 은 모든 자연수를 나타냅니다.
정규 표현식을 사용하여 기호 발생을 나타내는
문자=또는
숫자=또는|0|1|2|3|4|5|6|7|8|9
기호=
정규 표현식을 사용하여 언어 토큰을 나타냅니다.
십진수=(기호)?(숫자)+
식별자=(문자)(문자|숫자)*
유한 오토마타
이것은 입력 기호를 통한 상태 및 전환에 초점을 맞춘 5 개의 튜플(큐,2483>
)의 조합입니다.
기호 문자열을 입력으로 취하여 패턴을 인식하고 그에 따라 상태를 변경합니다.
유한 오토마타의 수학적 모델은 다음으로 구성됩니다;입력 기호의 유한 집합(큐)
유한 오토마타는 어휘 분석에 사용되어 입력 프로그램에서 식별자,키워드 및 상수 형태로 토큰을 생성합니다.
유한 오토마타는 정규식 문자열을 공급하고 상태는 각 리터럴에 대해 변경됩니다.
입력이 성공적으로 처리되면,오토마타는 최종 상태에 도달하고,그렇지 않으면 거부된다.
유한 오토마타의 구성
하자 엘(아르 자형)일부 유한 오토마타에 의한 정규 언어 에프(에이).
그러므로;
- 상태:원은 빠의 상태를 나타냅니다 그들의 이름은 원 안에 기록됩니다.
- 시작 상태:오토마타가 시작되는 상태입니다. 그것은 그것을 향해 가리키는 화살표를해야합니다.
- 중간 상태:두 개의 화살표가 있는데,하나는 그것을 가리키고 다른 하나는 중간 상태를 가리킨다.
- 최종 상태: 오토마타는 입력 문자열이 성공적으로 구문 분석되고 이중 원으로 표현 된 경우 최종 상태가 될 것으로 예상되며 그렇지 않으면 입력이 거부됩니다. 그것은 그것을 가리키는 홀수의 화살표와 그것으로부터 가리키는 짝수,즉
홀수 화살표=짝수 화살표+1 을 포함 할 수 있습니다. - 전환:입력에서 원하는 기호가 발견되면 한 상태에서 다른 상태로의 전환이 발생합니다. 오토마타는 다음 상태로 이동하거나 지속됩니다.
방향 화살표는 대상 상태를 가리키는 동안 한 상태에서 다른 상태로 이동을 표시합니다.
오토마타가 같은 상태를 유지하면 상태에서 그 자체를 가리키는 화살표가 그려집니다.
예를 들어,1 로 끝나는 3 자리 이진 값이 파에 의해 허용된다고 가정합니다.
그 FA={Q(q0,qf),Σ(0,1),q0,qf,δ}
사이 관계는 정규 표현식 및 오토마타 유한
사이의 관계는 일반현 및 오토마타 유한은 다음과 같습니다;
아래 그림은 쉽게 변환 할 수 있음을 보여줍니다;
- 비 결정적 유한 오토마타에 대한 정규 표현식.
- 비결정적유한한 오토마타로 이동한다.
- 정규 표현식에 대한 결정 론적 유한 오토마타.
렉스는 정규 표현식을 입력으로 받아들이고 정규 표현식을 인식하는 유한 오토 마톤을 시뮬레이션하는 프로그램을 반환합니다.
따라서 렉스는 문자열 패턴 생성(렉스에 대한 관심 문자열을 정의하는 정규 표현식)과 문자열 패턴 인식(관심있는 문자열을 인식하는 유한 오토 마톤)을 결합합니다.
가장 긴 일치 규칙
스캔한 어휘는 사용 가능한 모든 토큰 중 가장 긴 일치를 기반으로 결정되어야 한다고 명시합니다.
이것은 입력 스트림에서 다음 토큰을 결정할 때 모호성을 해결하는 데 사용됩니다.
소스 코드를 분석하는 동안 어휘 분석기는 코드 문자를 문자로 스캔하고 연산자,특수 기호 또는 공백이 감지되면 단어가 완료되었는지 여부를 결정합니다.
예:
int intvalue;위의 내용을 스캔하는 동안 분석기는’지능’이 키워드인지 식별자 지능값의 접두사인지 확인할 수 없습니다.
규칙 우선 순위가 적용되어 키워드에 사용자 입력보다 우선 순위가 부여되며,이는 위의 예에서 분석기가 오류를 생성한다는 것을 의미합니다.
어휘 오류
문자 시퀀스를 유효한 토큰으로 스캔할 수 없을 때 어휘 오류가 발생합니다.
이러한 오류는 식별자,키워드 또는 연산자의 맞춤법이 잘못되어 발생할 수 있습니다.
일반적으로 매우 드문 어휘 오류는 토큰의 잘못된 문자로 인해 발생합니다.
오류 수;
- 맞춤법 오류.
- 두 문자의 조옮김.
- 잘못된 문자.
- 식별자 또는 숫자 상수의 길이를 초과합니다.
- 문자를 잘못된 문자로 대체
- 있어야 할 문자를 제거합니다.
오류 복구 수반;
- 나머지 입력에서 한 문자 제거
- 인접한 두 문자 전치
- 나머지 입력에서 한 문자 삭제
- 나머지 입력에 누락된 문자 삽입
- 문자를 다른 문자로 바꿉니다.
- 법적 토큰이 형성 될 때까지 연속 문자를 무시합니다(패닉 모드 복구).
오류 복구 체계
패닉 모드 복구.
이 오류 복구 체계에서 어휘 분석기가 나머지 입력의 시작 부분에서 잘 형성된 토큰을 찾을 수있을 때까지 나머지 입력에서 일치하지 않는 패턴이 삭제됩니다.
더 쉬운 구현은 이 접근법의 장점입니다.
추가 오류를 확인하지 않고 많은 양의 입력을 건너뛰는 제한이 있습니다.
로컬 수정.
포인트 삽입/삭제 및/또는 대체 작업에서 오류가 감지되면 잘 형성된 텍스트가 달성 될 때까지 실행됩니다.
결과 새 텍스트를 입력으로 사용하여 분석기가 다시 시작됩니다.
전역 수정.
로컬 보정이 실패할 경우 향상된 패닉 모드 복구가 선호됩니다.
시간 및 공간 요구 사항이 높기 때문에 실질적으로 구현되지 않습니다.
어휘 분석기 필요
- 컴파일러 효율성 향상-문자를 읽기 위한 특수 버퍼링 기술은 컴파일러의 프로세스 속도를 높입니다.
- 컴파일러 디자인의 단순성-공백 및 주석을 제거하면 구문 분석기에 대한 효율적인 구문 구조를 사용할 수 있습니다.
- 컴파일러 이식성-스캐너만 외부 세계와 통신합니다.
- 전문화-전문 기술을 사용하여 어휘 분석 프로세스를 개선 할 수 있습니다.
어휘 분석 문제
- 둘러보기
입력 문자열이 주어지면 문자를 왼쪽에서 오른쪽으로 하나씩 읽습니다.
토큰이 완료되었는지 여부를 확인하려면 다음 문자를 확인해야 합니다.
예:’=’대입 연산자 또는’==’연산자의 첫 번째 문자입니다.
잘 구성된 토큰이 발견 될 때까지 미리보기가 입력에서 문자를 건너 뛰고 잘못된 기호와 같은 간단한 오류를 제외하고는 중요한 오류를 잡을 수 없음을 보여줍니다. - 모호성
렉스로 작성된 프로그램은 모호성 사양을 허용하므로 가장 긴 일치를 선택하고 여러 표현식이 입력과 일치하면 가장 긴 일치가 선호되거나 일치 규칙 중 첫 번째 규칙이 우선 순위 지정됩니다. - 예약 키워드
특정 언어는 다른 프로그래밍 언어에서 예약되지 않은 예약어를 가지고 있다.
그리고 문 주어진 할 10 리터=10,86,할 키워드
이러한 진술은 해결을 위해 미리 상당한 모습을 필요로한다.
컴파일러에서 사용하는 응용 프로그램
- 구문 분석 된 코드에서 준수 된 이진 실행 파일을 만듭니다.
- 웹 브라우저에서 웹 페이지를 포맷하고 표시하는 데 사용됩니다.
이 문서에서는 컴파일러 디자인에서 어휘 분석에 대한 강력한 아이디어를 가지고 있어야 합니다.