U E D R , A S I H C RSS
ZeroWiki

Programming Language Class/Report2002_1

Principles of Programming Languages

HW #1 3/27/2002

< 문 제 >

β€» μž…λ ₯된 λ¬Έμž₯듀이 μ œμ‹œλœ 문법(grammar)에 λ§žλŠ”μ§€ νŒλ‹¨ν•˜λŠ” Recursive Descent Parsing 기법을 μ΄μš©ν•œ νŒŒμ„œ(parser)λ₯Ό μž‘μ„±ν•˜μ‹œμ˜€.

< 일 μ • >

  • 제좜일: 4μ›” 10일(A반)
  • 데λͺ¨ λ‚ μ§œ: 4μ›” 10일(A반)
  • 제좜물
    • Internal/external documentations
    • ν”„λ‘œκ·Έλž¨ μ†ŒμŠ€μ½”λ“œ 및 μ‹€ν–‰νŒŒμΌμ΄ λ“  λ””μŠ€μΌ“

< λ¬Έ 법 > 

~cpp 
<start>              β†’ <statements>
<statements>       β†’ <statement>
              |  <statement> <semi_colon> <statements>
<statement> β†’ <identifier> <assignment_operator> <expression>
<expression> β†’ <term> <plus_operator> <expression>
              |  <term> <minus_operator> <expression>
              |  <term>             
<term>              β†’ <factor> <star_operator> <term>
              |  <factor> <slash_operator> <term>
              |  <factor>
<factor>     β†’ <left_parenthesis> <expression> <right_parenthesis>
              |  <identifier>
              |  <constant>
              |  <identifier><condition><identifier><question_operator><compare_value>
<condition>  β†’ <less_keyword> | <greater_keyword> | <equal_keyword>
<compare_value>    β†’ <identifier> <colon> <identifier>
<constant>  β†’ any decimal numbers
<identifier> β†’ any names conforming C identifier

<question_operator> β†’ ?
<less_keyword>        β†’ <
<greater_keyword>  β†’ >
<equal_keyword>    β†’ ==
<colon>        β†’ :
<assignment_operator> β†’ =
<semi_colon>       β†’ ;
<plus_operator>     β†’ +
<minus_operator>   β†’ -
<star_operator>     β†’ *
<slash_operator>    β†’ /
<left_parenthesis> β†’ (
<right_parenthesis> β†’ )

< μ„ΈλΆ€ 사항 >

  • μž…λ ₯: INPUT.TXT둜 이름지어진 ν…μŠ€νŠΈ 파일
  • 좜λ ₯: 주어진 문법에 따라 INPUT.TXT에 μ €μž₯λ˜μ–΄ μžˆλŠ” λ¬Έμž₯을 λΆ„μ„ν•œλ‹€. νŒŒμ‹±(parsing)λ˜λŠ” 쀑간과정을 <처리 예>와 같이 좜λ ₯ν•˜κ³ , 문법에 μ ν•©ν•˜λ©΄ β€œYes,” μž…λ ₯된 λ¬Έμž₯이 μ ν•©ν•˜μ§€ μ•ŠμœΌλ©΄ 였λ₯˜ λ©”μ‹œμ§€μ™€ β€œNo”λ₯Ό 좜λ ₯ν•œλ‹€.
  • 처리 쑰건
    • 각 νŒŒμ‹±(parsing) ν•¨μˆ˜λŠ” λ¦¬ν„΄ν•˜κΈ° 직전에 ν•΄λ‹Ή non-terminal이 κ²€μƒ‰λ˜μ—ˆμŒμ„ μ•Œλ¦¬λŠ” λ©”μ‹œμ§€λ₯Ό 좜λ ₯ν•˜μ—¬μ•Ό ν•œλ‹€.

~cpp 
      예)     void expression(void) {

                      ...

                      printf("<expression> parsed.\n");

              }
  • <identifier>와 <constant>의 κ²½μš°μ—λŠ” 찾아진 lexeme을 ν•¨κ»˜ 좜λ ₯ν•œλ‹€.

~cpp 
      예)     void identifier(void) {

                      ...

                      printf("<identifier>: %s parsed.\n",token_string);

              }
  • μž…λ ₯ μŠ€νŠΈλ¦Όμ—μ„œ ASCII μ½”λ“œλ‘œ 32 μ΄ν•˜μΈ 것은 λͺ¨λ“  white-space둜 κ°„μ£Όν•˜λ©°, white-spaceλŠ” 각 token을 κ΅¬λ³„ν•˜λŠ” μš©λ„ μ΄μ™Έμ—λŠ” λͺ¨λ‘ λ¬΄μ‹œν•œλ‹€.
  • μ–΄νœ˜λΆ„μ„κΈ°(lexical analyzer)의 μ†ŒμŠ€μ½”λ“œλŠ” μ •μˆ˜ λ³€μˆ˜ next_token, λ¬Έμžμ—΄ λ³€μˆ˜ token_string, ν•¨μˆ˜ lexical()을 ν¬ν•¨ν•˜μ—¬μ•Ό ν•œλ‹€. ν•¨μˆ˜ lexical()은 μž…λ ₯ μŠ€νŠΈλ¦Όμ„ λΆ„μ„ν•˜μ—¬ ν•˜λ‚˜μ˜ lexeme을 μ°Ύμ•„λ‚Έ λ’€, κ·Έκ²ƒμ˜ token type을 next_token에 λŒ€μž…ν•˜κ³ , lexeme λ¬Έμžμ—΄μ„ token_string에 μ €μž₯ν•˜λŠ” ν•¨μˆ˜μ΄λ‹€.
  • λ¬Έμž₯이 문법에 μ ν•©ν•˜μ§€ μ•ŠμœΌλ©΄ κ΄€λ ¨ 였λ₯˜ λ©”μ‹œμ§€λ₯Ό 좜λ ₯ν•œλ‹€. κ·Έ λ‹€μŒ 였λ₯˜λ₯Ό λ°œμƒμ‹œν‚¨ lexeme을 제거 λ˜λŠ” μ²¨κ°€ν•œ ν›„, νŒŒμ‹±μ„ μž¬κ°œν•œλ‹€. 예λ₯Ό λ“€μ–΄, x = a + + b일 경우, β€œ+” μ—°μ‚°μžκ°€ ν•œ κ°œκ°€ 더 μ‘΄μž¬ν•˜λ―€λ‘œ 였λ₯˜ λ©”μ‹œμ§€λ₯Ό 좜λ ₯ν•œλ‹€. κ·Έ λ‹€μŒ, β€œ+β€κΈ°ν˜Έλ₯Ό μ œκ±°ν•œ ν›„ νŒŒμ‹±μ„ κ³„μ†ν•œλ‹€.
  • 기타 κ΅¬ν˜„ μ‹œ μš”κ΅¬λ˜λŠ” μ„ΈλΆ€ 사항은 직접 κ²°μ •ν•˜κ³ , internal document에 κΈ°μˆ ν•œλ‹€.
  • 데λͺ¨ μ‹œ λ””μŠ€μΌ“μ— μ‹€ν–‰νŒŒμΌμ„ 미리 μ€€λΉ„ν•œλ‹€(데λͺ¨ μ‹œμ— μ»΄νŒŒμΌν•˜λŠ” κ²½μš°λŠ” κ°μ μ²˜λ¦¬ν•¨).

< 처리 예 >

  • μž…λ ₯: target = operand1 + operand2 * 428
  • 좜λ ₯ 

~cpp 
      <identifier>: target parsed. 
      <assignment_operator> parsed. 
      <identifier>: operand1 parsed. 
      <factor> parsed. 
      <term> parsed. 
      <plus_operator> parsed. 
      <identifier>: operand2 parsed. 
      <factor> parsed. 
      <star_operator> parsed. 
      <constant>: 428 parsed. 
      <factor> parsed. 
      <term> parsed. 
      <term> parsed. 
      <expression> parsed. 
      <expression> parsed. 
      <statement> parsed. 
      <statements> parsed. 
      <start> parsed. 
      Yes!!

  • μž…λ ₯: target = operand1 + + operand2
  • 좜λ ₯ 

~cpp 
      <identifier>: target parsed. 
      <assignment_operator> parsed. 
      <identifier>: operand1 parsed. 
      <factor> parsed. 
      <term> parsed. 
      <plus_operator> parsed. 
      ERROR : plus-operator 
      <identifier>: operand2 parsed. 
      <factor> parsed. 
      <term> parsed. 
      <expression> parsed. 
      <expression> parsed. 
      <statement> parsed. 
      <statements> parsed. 
      <start> parsed. 
      No!!

  • μž…λ ₯: target = op1 > op2 ? op3 : op4 * op5
  • 좜λ ₯ 

~cpp 
      <identifier>: target parsed. 
      <assignment_operator> parsed. 
      <identifier>: op1 parsed. 
      <greater_keyword> parsed. 
      <condition> parsed. 
      <identifier>: op2 parsed. 
      <question_operator> parsed. 
      <identifier>: op3 parsed. 
      <colon> parsed. 
      <identifier>: op4 parsed 
      <compare_value> parsed. 
      <factor> parsed. 
      <star_operator> parsed. 
      <identifier>: op5 parsed. 
      <factor> parsed. 
      <term> parsed. 
      <term> parsed. 
      <expression> parsed. 
      <statement> parsed. 
      <statements> parsed. 
      <start> parsed. 
      YES!!
  • μž…λ ₯: target = op1 > op2 ? op3
  • 좜λ ₯ 

~cpp 
      <identifier>: target parsed. 
      <assignment_operator> parsed. 
      <identifier>: op1 parsed. 
      <greater_keyword> parsed. 
      <condition> parsed. 
      <identifier>: op2 parsed. 
      <question_operator> parsed. 
      <identifier>: op3 parsed. 
      ERROR : colon 
      <compare_value> parsed. 
      <factor> parsed. 
      <term> parsed. 
      <expression> parsed. 
      <statement> parsed. 
      <statements> parsed. 
      <start> parsed. 
      NO!!
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:24:03
Processing time 0.0144 sec