Lec09. Lexer & Parser Generators - 10주차 2강

11월 6일 - 10주차 2강

* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다.

 

Goal: Useful Tools for Compiler Construction

• Lexing and Parsing algorithm
  • Lexer: Thompson 알고리즘 및 Subset 구성
  • Parser: top-down, bottom-up
• 컴파일러 제작 도구
  • lexer, parser 수동으로 안만들어도 됨. ocamllex, ocamlyacc로 자동화 가능
  • ocamlyacc: LALR, OCaml용 parser 생성기(구문분석기)
  • ocamllex: OCaml용 lexer 생성기(어휘분석기)

Compiler Construction with ocamllex and ocamlyacc

• 전반적으로 파일 구조를 설명하고 있음
• 입력
  • Regex: 어휘분석 lexing을 위한 규칙 정의 lexer.mll 파일
  • CFG: 구문분석 parsing을 위한 규칙 정의, parser.mly 파일
• generator
  • lexer generator: 어휘 분석기 생성기, ocamllex 사용
  • parser generaator: 구문 분석기 생성기, ocamlyacc 사용
• 출력 output
  • lexer source code, parse source code를 기존 Ocaml 등의 컴파일러로 컴파일
  • 최종적으로 parser+lexer 형태의 실행 가능한 a.out 파일이 만들어짐

• 예시로 계산기를 구현하는 경우
  • ast.ml: abstract syntax tree의 정의와 평가 함수가 포함된 파일
  • parser.mly: ocamlyacc용 입력 파일, 산술표현식의 context free grammar 정의
  • lexer.mll: ocamllex용 입력 파일, 정규 표현식으로 어휘 분석 규칙 정의
  • main.ml: 프로그램 실행의 시작점
  • 산술 표현식 입력->어휘 분석(lexer)->구문분석(parser)->AST생성 및 평가

• type expr: 산술표현식을 정의하는 데이터 타입
• eval: 산술 표현식에 대한 결과를 계산해 반환. 재귀적으로 호출된다.
  • Add (Num 1, Num 2) → (eval (Num 1)) + (eval (Num 2)) → 1 + 2 → 3
  • Mul (Num 3, Add (Num 1, Num 2)) → (eval (Num 3)) * (eval (Add (Num 1, Num 2))) → 3 * 3 → 9

• %{......%} user declarations 사용자 선언, 구문분석기에서 사용할 OCaml 선언 작성
• parser declarations: 구문분석기 선언, 연산자 우선순위, 종단기호, 결합성 등
• %% 이후: production rules 정의. 문법을 정의

• 토큰은 연산을 지칭하는 대명사.
• Token 선언 (%token):
  • %token NEWLINE LPAREN RPAREN PLUS MINUS MULTIPLY:
    • 이들은 터미널 심볼(토큰)의 이름으로, 각각 특정 입력을 의미.
    • 예: PLUS는 +, MULTIPLY는 *, LPAREN/RPAREN는 (/)를 의미.
  • %token <int> NUM:
    • 값(int)을 가지는 토큰은 타입을 명시해야 함.
    • 여기서 NUM은 숫자를 나타내며, 타입은 정수(int).
• Start Symbol 선언 (%start):
  • %start program:
    • 문법의 시작 심볼을 정의. 여기서는 program이 시작 심볼.
• Type 선언 (%type):
  • %type <Ast.expr> program:
    • 시작 심볼(program)의 타입을 지정. 여기서는 Ast.expr 타입 사용.
• Grammar Rules (문법 규칙):
  • program -> exp NEWLINE { $1 }:
    • program은 exp와 NEWLINE으로 구성. $1은 exp의 값을 반환.
  • exp -> NUM { Ast.Num $1 }:
    • exp가 숫자(NUM)로 구성될 경우, AST 노드 Ast.Num을 생성.
    • $1: NUM 토큰의 값.
  • exp -> exp PLUS exp { Ast.Add ($1, $3) }:
    • exp는 exp + exp로 구성되며, AST에서 Ast.Add 노드를 생성.
    • $1: 첫 번째 exp의 값, $3: 세 번째 exp의 값.
  • exp -> LPAREN exp RPAREN { $2 }:
    • exp가 괄호로 감싸인 경우, 괄호를 제거하고 exp 값 $2를 반환

• 입력 스트림을 순차적으로 읽어서 정규 표현식에 매칭되는 입력을 해당 토큰으로 변환함

 

• 대부분의 파서에서는 shift가 reduce보다 우선된다. 그래서 3+1이 먼저 계산됨
• 문제 해결법
  • 덧셈과 곱셈의 우선순위와 결합성 associativity를 정의
  • %left PLUS MINUS /* 덧셈과 뺄셈은 왼쪽 결합*/
  • %left MULTIPLY DIV /* 곱셈과 나눗셈은 덧셈보다 높은 우선순위 */
  • 그리고 위에 선언된 게 우선순위가 높은 규칙이라서 더 먼저 선언하면 됨

 

 

 

포스트 작성 노동요(지떨브)

https://youtu.be/r2ko422xW0w?si=mnB7_Wtf3Sm1MNHB

 

이 앞에 잔챙이 빨리 쳐내고 뒤에 "진짜" 공부하러 가야 됨