컴 파일 원리 실험 3 LR (1) 분석 법

실험 삼 LR (1) 분석 법
LR (1) 분석 프로그램 을 구성 하고 이 를 이용 하여 문법 분석 을 하여 제 시 된 기호 문자열 이 이 문법 으로 식 별 된 문장 인지 판단 하고 LR (K) 분석 방법 이 엄격하게 왼쪽 에서 오른쪽으로 스 캔 하고 아래 에서 위로 문법 분석 방법 임 을 파악 한다.
실험 내용
다음 문법 을 LR (1) 분석 법 으로 임의로 입력 한 기호 열 을 분석 합 니 다. (1) E - > E + T (2) E - > T (3) T - > T * F
(4)T->F (5)F-> (E) (6)F-> i
3. LR (1) 분석 법 실험 디자인 사상 과 알고리즘
(1) 총 제어 프로그램 은 드라이버 라 고도 할 수 있다.모든 LR 분석 기 에 대한 총 제어 프로그램 은 같다.(2) 분석 표 나 분석 함 수 는 서로 다른 문법 분석 표 가 다 르 고 같은 문법 이 사용 하 는 LR 분석 기 가 다 르 며 분석 표 가 다 르 며 분석 표 는 동작 표 (ACTION) 와 상태 전환 (GOTO) 표 두 부분 으로 나 눌 수 있 는데 모두 2 차원 배열 로 표시 할 수 있다.(3) 분석 스 택 은 문법 기호 스 택 과 해당 하 는 상태 스 택 을 포함 하고 모두 선진 적 인 후에 스 택 을 나 간다.분석 기의 동작 은 스 택 정상 상태 와 현재 입력 기호 에 의 해 결정 된다.
『 61557 』 LR 분석 기 는 세 부분 으로 구성 되 어 있 습 니 다.
16
그 중에서 SP 는 스 택 포인터 이 고 S [i] 는 상태 스 택 이 며 X [i] 는 문법 기호 스 택 입 니 다.상태 변환 표 는 GOTO [i, X] = j 로 표시 하 며 스 택 의 맨 위 상 태 를 i 로 규정 하고 현재 문법 기호 가 X 일 때 상태 j, X 는 종결 부 또는 비 종결 부 로 전환 해 야 한다.
『 61557 』 ACTION [i, a] 은 스 택 정상 상태 가 i 일 때 입력 기호 a 를 만나면 실행 해 야 한다 고 규정 했다.동작 은 네 가지 가능성 이 있다.
(1) 이동: action [i, a] = Sj: 상태 j 를 상태 스 택 으로 옮 기 고 a 를 문법 기호 스 택 으로 옮 깁 니 다. 그 중에서 i, j 표.
상태 번호.(2) 귀 약:
action [i, a] = rk: 스 택 꼭대기 에서 핸들 을 형성 할 때 해당 하 는 비 종결 부 A 로 요약 합 니 다. 즉, 문법 에 A - B 의 생 성 식 이 있 습 니 다. 만약 에 B 의 길이 가 R (즉 | B | = R) 이면 상태 스 택 과 문법 기호 스 택 에서 위 에서 아래로 R 개의 기 호 를 제거 합 니 다. 즉, 스 택 포인터 SP 에서 R 을 빼 고 A 를 문법 기호 스 택 에 옮 깁 니 다. j = GOTO [i, A] 는 상태 스 택 으로 옮 깁 니 다.그 중에서 i 는 지침 을 수정 한 스 택 의 정상 상태 입 니 다.(3) 받 는 acc:
문법 기호 스 택 에 문법 시작 기호 S 만 남 았 을 때 입력 기호 문자열 이 끝 났 습 니 다. 즉, 현재 입력 문자 가 '\ #' 이면 분석 에 성공 합 니 다.(4) 오류 보고:
상태 스 택 상단 이 특정한 상태 에서 만 나 지 말 아야 할 문법 기호 가 나타 날 때 오 류 를 보고 하 는 것 은 입력 단 이 이 문법 이 받 아들 일 수 있 는 기호 문자열 이 아니 라 는 것 을 의미한다.
17
4. 실험 요구
1. 프로 그래 밍 할 때 프로 그래 밍 스타일 에 주의 하 십시오. 빈 줄 의 사용, 주석 의 사용, 들 여 쓰기 사용 등 입 니 다.2. 잘못된 표현 식 에 부 딪 히 면 오류 알림 정 보 를 출력 해 야 합 니 다.3. 프로그램 입 출력 인 스 턴 스: \ # 로 끝 나 는 기호 문자열 (+ * () i \ # 포함) 을 입력 하 십시오. 이 위치 에서 기호 문자열 출력 과정 은 다음 과 같 습 니 다.
단계 상태 창고 기호 창고 남 은 입력 문자열 동작 10 \ # i + i * i \ # 이동
i + i * i 의 LR 분석 과정
순서
상태 스 택
기호 창고
입력 문자열
동작 설명
1
0
#
i+i*i#
ACTION [0, i] = S5, 상태 5 입 점
2
05
#i
+i*i#
r6: F → i 귀 약, GOTO (0, F) = 3 입 점
3
03
#F
+i*i#
r4: T → F 귀 약, GOTO (0, T) = 3 입 점
4
02
#T
+i*i#
r2: E → T 귀 약, GOTO (0, E) = 1 입 점
18
5
01
#E
+i*i#
ACTION [1, +] = S6, 상태 6 입고
6
016
#E+
i*i#
ACTION [6, i] = S5, 상태 5 입고
7
0165
#E+i
*i#
r6: F → i 귀 약, GOTO (6, F) = 3 입 점
8
0163
#E+F
*i#
r4: T → F 귀 약, GOTO (6, T) = 9 입 점
9
0169
#E+T
*i#
ACTION [9, *] = S7, 상태 7 입고
10
01697
#E+T*
i#
ACTION [7, i] = S5, 상태 5 입고
11
016975
#E+T*i
#
r6: F → i 귀 약, GOTO (7, F) = 10 입 점
12
0169710
#E+T*F
#
r3: T → T * F 귀 약, GOTO (6, T) = 9 입 점
13
0169
#E+T
#
r1: E → E + T, GOTO (0, E) = 1 입고
14
01
#E
#
Acc: 분석 성공
4. 기호 문자열 을 불법 기호 문자열 로 입력 (또는 합 법 적 인 기호 문자열 로 입력)
산술 식 문법 의 LR 분석 표
상태.
ACTION
GOTO
i
+
*
(
)
#
E
T
F
0
S5
 
 
S4
 
 
1
2
3
1
 
S6
 
 
 
acc
 
 
 
2
 
r2
S7
 
r2
r2
 
 
 
3
 
r4
r4
 
r4
r4
 
 
 
4
S5
 
 
S4
 
 
8
2
3
5
 
r6
r6
 
r6
r6
 
 
 
6
S5
 
 
S4
 
 
 
9
3
7
S5
 
 
S4
 
 
 
 
10
8
 
S6
 
 
S11
 
 
 
 
9
 
r1
S7
 
r1
r1
 
 
 
10
 
r3
r3
 
r3
r3
 
 
 
11
 
r5
r5
 
r5
r5
 
 
 
5. 실험 절차
1. 프로 세 스 맵 에 따라 각 모듈 의 소스 코드 를 작성 하여 컴퓨터 로 디 버 깅 합 니 다.
19
2. 소스 프로그램 을 작성 한 후에 몇 가지 사례 를 디자인 하여 시스템 에 대해 전면적 인 온라인 테스트 를 하고 디자인 된 LR (1) 문법 분석 절 차 를 통과 한다.완전히 만 족 스 러 운 결 과 를 얻 을 수 있 을 때 까지.3. 실험 보고 서 를 작성 한다.실험 보고서 의 본문 내용:

  LR (1) 문법 분석 프로그램의 디자인 사상 을 묘사 하 다

  프로그램 구조 설명: 함수 호출 형식, 매개 변수 의미, 반환 값 설명, 함수 기능;함수 간 호출 관계 도..

  상세 한 알고리즘 설명

  소프트웨어 의 테스트 방법 과 테스트 결 과 를 제시 하 다.『 61557 』 실험 총화 (디자인 의 특징, 부족, 수확 과 체험)

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Q3 {
    StringBuilder input = new StringBuilder();

    Deque sStack = new LinkedList<>();
    Deque cStack = new LinkedList<>();

    void start() throws IOException {
        InputStreamReader reader = new InputStreamReader(Q2.class.getResourceAsStream("Q2"));
        for(int ch; (ch = reader.read()) != -1; ){
            input.append((char)ch);
        }

        sStack.add(0);
        cStack.add('#');

        int s = sStack.getLast();
        char a = input.charAt(0);

        while(true){
            String temp = ACTION.get(s).get(a);
            if(temp == null){
                print("ERROR");
                break;
            }else if(temp.startsWith("r")){
                print("");
                int index = Integer.parseInt(temp.substring(1));
                int length = production[index][1].length();
                while(length-- != 0){
                    sStack.removeLast(); cStack.removeLast();
                }
                cStack.add(production[index][0].charAt(0));
                if(GOTO.get(sStack.getLast()).get(cStack.getLast()) == null){
                    print("ERROR");
                    break;
                }
                s = GOTO.get(sStack.getLast()).get(cStack.getLast());
                sStack.add(s);
            }else if(temp.startsWith("S")){
                print("");
                sStack.add(Integer.parseInt(temp.substring(1)));
                s = sStack.getLast();
                cStack.add(a);
                input.deleteCharAt(0);
                a = input.charAt(0);
            }else {
                print("SUCCESS");
                break;
            }
        }
    }

    void print(String msg){
        if("ERROR".equals(msg)){
            System.out.println(msg);
        }else if("SUCCESS".equals(msg)){
            System.out.println(sStack.toString() + '\t' + cStack.toString() + '\t' + input.toString() + '\t' + msg);
        }else {
            System.out.println(sStack.toString() + '\t' + cStack.toString() + '\t' + input.toString());
        }
    }


    static List