compiler

📠 2021-1 Compiler

과제 1: DFA Implementation

요구 사항

Hardwired method

Table-driven method

DFA를 Hardwired method와 Table-driven method로 구현하고 다음 2가지 상황을 테스트 하라.

• 
• 

실행 화면

Hardwired method

Table-driven method

과제 2: Lexical Analyzer

요구 사항

정의한 special form token과 general form token이 포함된 sample program을 작성하여 구현한 어휘 분석기를 실행하기

• Sample program은 negative example도 포함하도록 하여 error를 출력하는 것을 확인할 수 있어야 함
• 데모를 통해 token이 올바르게 인식되었음을 쉽게 확인할 수 있도록 하고, 인식 과정에서 생성한 symbol table과 literal table을 보여주어야 함
• 처리 항목 - Bold: required, Italic: optional
• Special form tokens
• Keywords
• Special symbols
• General form tokens
• Identifier
• Literal/Constants
• Number
• Decimal
• Octal
• Hexdecimal
• String

실행 방법 및 화면

• How to run this program

  LexicalAnalyzer.exe <input-file> <output-file>
  

• Sample program: input-file.py

  def foo(count):
    res = 0
    for i in range(1, count + 1):
        res += i
    print("{} times completed".format(count))
    return res
    
  # This is comment. ← Because # is not defined, it will cause error!
    foo(5)
  

• Analysis result: output-file.txt

  ==========================[ Token Table ]==========================
  (21, -) (Token.SPACE, -) (Token.ID, 1) (Token.LPAREN, -) (Token.ID, 2) (Token.RPAREN, -) (Token.COLON, -) (Token.NEWLINE, -)
  (Token.SPACE, -) (Token.SPACE, -) (Token.SPACE, -) (Token.SPACE, -) (Token.ID, 3) (Token.SPACE, -) (Token.ASSIGNMENT2, -) (Token.SPACE, -) (Token.ZERO, -)(Token.NEWLINE, -)
  (Token.SPACE, -) (Token.SPACE, -) (Token.SPACE, -) (Token.SPACE, -) (17, -) (Token.SPACE, -) (Token.ID, 4) (Token.SPACE, -) (8, -) (Token.SPACE, -)(Token.ID, 5) (Token.LPAREN, -) (Token.DECIMAL, -) (Token.COMMA, -) (Token.SPACE, -) (Token.ID, 2) (Token.SPACE, -) (Token.PLUS, -) (Token.SPACE, -)(Token.DECIMAL, -) (Token.RPAREN, -) (Token.COLON, -) (Token.NEWLINE, -)
  (Token.SPACE, -) (Token.SPACE, -) (Token.SPACE, -) (Token.SPACE, -) (Token.SPACE, -) (Token.SPACE, -) (Token.SPACE, -) (Token.SPACE, -) (Token.ID, 3) (Token.SPACE, -) (Token.ADD_ASSIGNMENT, -) (Token.SPACE, -) (Token.ID, 4) (Token.NEWLINE, -)
  (Token.SPACE, -) (Token.SPACE, -) (Token.SPACE, -) (Token.SPACE, -) (Token.ID, 6) (Token.LPAREN, -) (Token.STRING2, -) (Token.PERIOD, -) (Token.ID, 7) (Token.LPAREN, -) (Token.ID, 2) (Token.RPAREN, -) (Token.RPAREN, -) (Token.NEWLINE, -)
  (Token.SPACE, -) (Token.SPACE, -) (Token.SPACE, -) (Token.SPACE, -) (14, -) (Token.SPACE, -) (Token.ID, 3) (Token.NEWLINE, -)
  (Token.NEWLINE, -)
  
  !!! Error occurred because of the symbol # !!!
  
  ==========================[ Symbol Table ]=========================
  (1) foo
  (2) count
  (3) res
  (4) i
  (5) range
  (6) print
  (7) format
  
  =========================[ Literal Table ]=========================
  (1) 0
  (2) 1
  (3) "{} times completed"
  

  
• Run Lexical Analyzer in command line

과제 3: PD Parser

요구 사항

제시한 문법과 파싱 테이블을 이용하여 aabccd, bccd에 대한 구문 분석을 수행하는 predictive parser를 구현하고 실행 과정을 보이기

• 문법
1. S → aS
2. S → bA
3. A → d
4. A → ccA
• 파싱 테이블

• 입력: aabccd
• 출력

실행 화면

과제 4: LR Parser

요구 사항

제시한 문법과 파싱 테이블을 이용하여 bottom-up parser를 구현하고 parsing 수행 결과를 보이기

• Grammar
1. E → E + T
2. E → T
3. T → T * F
4. T → F
5. F → (E)
6. F -> id
• Input
1. a * a + a
2. a + a * a
3. (a + a) * a
• 파싱 테이블

• 입력: a * a + a
• 출력

실행 화면

1. 입력: a * a + a

2. 입력: a + a * a

3. 입력: (a + a) * a