Principles of Programming Languages ¶
HW #1 3/27/2002
< λ¬Έ μ > ¶
β» μ
λ ₯λ λ¬Έμ₯λ€μ΄ μ μλ λ¬Έλ²(grammar)μ λ§λμ§ νλ¨νλ Recursive Descent Parsing κΈ°λ²μ μ΄μ©ν νμ(parser)λ₯Ό μμ±νμμ€.
< μΌ μ > ¶
- μ μΆμΌ: 4μ 10μΌ(Aλ°)
- λ°λͺ¨ λ μ§: 4μ 10μΌ(Aλ°)
- μ μΆλ¬Ό
- Internal/external documentations
- νλ‘κ·Έλ¨ μμ€μ½λ λ° μ€ννμΌμ΄ λ λμ€μΌ
- 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μ΄ κ²μλμμμ μ리λ λ©μμ§λ₯Ό μΆλ ₯νμ¬μΌ νλ€.
- κ° νμ±(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!!