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!! 

ProgrammingLanguageClass