낡은 독서 노트: 컴파일링 원리 (제2판) 노트

컴파일링 원리 (제2판) 노트
카탈로그
[숨기기]
간단한 문법 프로그래밍 번역기
1.1 오른쪽 결합 문법1.2 연산자 우선 순위1.32 의문법의 제거: 여기 분호가 stmt가 아닌 뒤에 있음을 주의한다1.4 귀속 하락: 왼쪽 귀속을 오른쪽 귀속으로 수정하고 e 증가
1.5 AST: 추상 구문 트리1.6 각 역할 영역에 대한 기호 테이블 설정1.7 정적 검사
2 문법 분석3 문법 분석
3.1 CFG
3.2 귀속 하강 문법 분석: FIRST, FOLLOW 집합 구하기
3.2.1 LL (1) 문법
3.3 밑에서 위로 문법 분석
3.3.1 이진-귀약
3.4 LR 분석기
3.4.1 LR(0)
3.4.2 SLR
3.4.3 규범 LR(1)3.4.4 LALR
3.4.52 의문법3.4.6 YACC


4 문법 유도 번역
4.1 SDD: 구문 프로그래밍 정의4.2 계승 속성과 종합 속성4.3 의존도4.4 SDD1:'S 속성'4.5 SDD2:'L 속성'
5 중간 코드 생성
5.1 DAG
5.2 유형 유도: 합일
6 런타임 환경
6.1'호출-반환'시퀀스6.2 활성 레코드 스택6.3 액세스 체인(access link)
7 코드 생성
7.1 대상 코드7.2 기본 블록7.3 흐름도7.4 부분적 최적화
8 기계 무관 최적화(전역 최적화)
8.1 데이터 흐름 분석8.2 상량 전파8.3 흐름도에서의 순환
8.3.1 지배 노드8.3.2 깊이 우선 순위8.3.3회변8.3.4 그림의 깊이8.3.5 귀약성
8.4구역 분석
9 명령 레벨 병렬 10 병행성 및 부분적 최적화
10.1 소스 코드 변환: 7개의 기본 모방 변환10.2 유수선화 기술
11 프로세스 간 분석
11.1 호출도11.2 상하문 관련11.3 Datalog 규칙11.4 상하문 관련 지침 분석
12 Comment
[편집] 간단한 문법 프로그래밍 번역기
[편집] 오른쪽 결합 문법
에 대한 값 a=b=c는 다음과 같습니다.

right  := left=right | letter
left   := letter
letter := a | b | c

[편집] 연산자 우선 순위
2개의 비종결자 expr,term를 생성하여 각각 이 두 우선순위(+-와 */)에 대응하고 다른factor를 도입하여 연산 기본 단원을 대표하며 둘 다 왼쪽으로 결합된 것을 고려하면 다음과 같다.

 term  := term * factor | term / factor | factor
 expr  := expr + term | expr - term | term
 factor:= DIGIT | ( expr )

비종결부 명칭에 대한 기교를 주의하십시오.
[편집] 이의문법의 해소: 여기 번호가 stmt 뒤에 있지 않도록 주의하세요.

 stmt  := ID = expr ;
        | if( expr ) stmt
        | if( expr ) stmt else stmt
        | while( expr ) stmt
        | do stmt while ( expr ) ;
        | { stmts }
 stmts := stmts stmt
        | e

[편집] 반복 하락: 왼쪽 반복을 오른쪽 반복으로 변경하고 e 증가
이전:

 A := Aa | b

다음:

 A := bR
 R := aR | e

[편집] AST: 추상 구문 트리
[편집] 각 역할 영역에 대한 기호 테이블 설정하기
[편집] 정적 검사
왼쪽, 오른쪽유형 일치
자동 유형 변환무거운 짐
어법 분석
버퍼: eof(-1) 표시정규 표현식Aho와Corasick은 KMP 알고리즘을 보급하여 하나의 키워드 집합 중의 모든 키워드(문자열 처리 분야의 4개 알고리즘/데이터 구조: KMP,BM,접미사 트리(수조),AC자동기)를 식별할 수 있도록 했다.
Lex
Fortran과 기타 일부 언어에서 키워드는 보존자가 아닙니다...(접미어 보기)FA
NFA에서 DFA로의 전환: e-Closure의 구조NFA의 on-the-fly 시뮬레이션(즉,'즉시 사용')DFA 중 사망 상태(미달)리에서 직접 구성한 DFA:nullable,firstpos,lastpos,followposDFA 최소화(제일 작은 게 유일한 거 아니야??)

DFA 스토리지

 int nextState(s,a){
     if( check[ base[s]+a ] == s ) return next[ base[s]+a ];
     else return nextState( default[s],a );
 }

[편집] 구문 분석
[편집] CFG
[편집] 귀속 하강 문법 분석:FIRST,FOLLOW 집합을 구한다(사실은 전달 클립이다)
[편집] LL (1) 문법
[편집] 밑에서 위로 문법 분석
[편집] 이입-귀약
[편집] LR 분석기
[편집] LR(0)
[편집] SLR
ACTION
GOTO
[편집] 사양 LR(1)
LR(1)항[편집] LALR
동일한 코어를 가진 LR (1) 항목 결합[편집] 이의문법
[편집] YACC
[편집] 문법 프로그래밍의 번역
[편집] SDD: 구문 프로그래밍 정의
[편집] 등록 정보 및 복합 등록 정보 상속
[편집] 의존도
[편집] SDD1:`S 속성]
모든 속성이 종합적[편집] SDD2:`L 속성]
계승 속성:parent 노드의 계승 속성과 왼쪽 형제의 (임의) 속성에만 의존할 수 있습니다
실제로 이것은 모든 일을 깊이 있게 처리할 수 있다는 것을 보장한다...

[편집] 중간 코드 생성
[편집] DAG
[편집] 유형 유도:일치
[편집] 런타임 환경
[편집] 호출 - 반환 시퀀스
[편집] 활성 레코드 스택
[편집] 액세스 체인(access link)
[편집] 코드 생성
[편집] 대상 코드
명령 집합 주소 공간: 코드, Static, Heap, Stack[편집] 기본 블록
[편집] 스트리밍
[편집] 부분 최적화
엿보기 최적화레지스터 할당트리 다시 쓰기[편집] 기계 무관 최적화(전역 최적화)
공통 하위 표현식복제 전파 [편집] 데이터 흐름 분석
도달 기준치활성 변수 분석사용 가능한 표현식[편집] 고정 전파
[편집] 흐름의 반복
[편집] 지정 노드
[편집] 깊이 우선순위 지정
[편집] Edge
[편집] 그림의 깊이
[편집] 애드온
[편집] 영역 분석
[편집] 명령 레벨 병렬
[편집] 병행성 및 부분적 최적화
[편집] 소스 코드 변환: 7개의 기본 모방 변환
융합(fusion)분열(fission)다시 인덱싱확대/축소역치(reversal)-역순환교환 (permutation) - 교환 내외 순환기울기(skewing) [편집] 유선화 기술
[편집] 프로세스 간 분석
[편집] 호출 그림
[편집] 컨텍스트 종속
[편집] Datalog 규칙
[편집] 컨텍스트 관련 포인터 분석
[편집]Comment