Skip to content

coding-Benny/compiler

Folders and files

NameName
Last commit message
Last commit date

Latest commit

ย 

History

91 Commits
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 

Repository files navigation

compiler

๐Ÿ“  2021-1 Compiler

๊ณผ์ œ 1: DFA Implementation

์š”๊ตฌ ์‚ฌํ•ญ

Hardwired method

state-transition-diagram.png

Table-driven method

state-transition-diagram.png

DFA๋ฅผ Hardwired method์™€ Table-driven method๋กœ ๊ตฌํ˜„ํ•˜๊ณ  ๋‹ค์Œ 2๊ฐ€์ง€ ์ƒํ™ฉ์„ ํ…Œ์ŠคํŠธ ํ•˜๋ผ.

์‹คํ–‰ ํ™”๋ฉด

Hardwired method

hardwired-dfa

Table-driven method

table-driven-dfa

๊ณผ์ œ 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"
    
    Analysis Result
  • Run Lexical Analyzer in command line 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
  • ํŒŒ์‹ฑ ํ…Œ์ด๋ธ”
  • parsing-table
  • ์ž…๋ ฅ: aabccd
  • ์ถœ๋ ฅ
  • desired result
์‹คํ–‰ ํ™”๋ฉด pd-parser result

๊ณผ์ œ 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
  • ํŒŒ์‹ฑ ํ…Œ์ด๋ธ”
  • parsing-table
  • ์ž…๋ ฅ: a * a + a
  • ์ถœ๋ ฅ
  • desired result desired result
์‹คํ–‰ ํ™”๋ฉด
  1. ์ž…๋ ฅ: a * a + a
  2. input1 result
  3. ์ž…๋ ฅ: a + a * a
  4. input2 result
  5. ์ž…๋ ฅ: (a + a) * a
  6. input3 result