[프로그래밍 언어 구조론]제6장 구문

제6장 구문

• 요기
• PL의 진리표 구문
• 기술 방법 및 제반에 대한 이해
  • 어휘 구조
  • 구문 구조: BNF, EBNF, 구문 다이어그램
  • 구문 분석 트리, 구문 트리 및 모호성
  • 구문 분석 기술 및 도구
  • 어휘 대 구문 대 의미론

구문과 의미

• 생김새: syntax: context-free grammer(중요)
  • 기술방법: bnf, extended bnf, syntax diagram
  • 처리방법(parser):top-down, bottom-up
• 의미-semetics(이 정도 있다만 알고 넘어가셈)
  • Static semantics: Attribute grammar
  • Dynamic semantics :-operational-aximomatic -denotational

•  

•  

개요

• 형식 언어 계층(Chomsky) - 컨텍스트프리만 알고가라, 갈수록 복잡
  • Regular 정기적인
  • Context-Free 컨텍스트 프리
  • Context-Sensitive 상황에 맞는
  • Unrestricted 무제한
• 프로그래밍 언어의 구문 구조
  • 어휘 구조(단어의 구조)
    • 정규표현식으로 표현 가능
  • 문법적인 구조(문장의 구조)
    • 문맥 자유 문법 context-free grammars (CFG)으로 표현 가능
    • BNF(Backus-Naur Form)는 CFG의 표기법일 뿐입니다.

어휘 구조

• 어휘 구조
  • 토큰의 구조
  • 토큰: 프로그래밍 언어의 단어
    • 기술적으로 토큰은 단어의 집합입니다.
• 정규식
• 토큰의 패턴을 설명하는 표현
• 텍스트 검색에 자주 사용

토큰

• 토큰 카테고리(C 예제 포함)
  • keywords 키워드(종종 예약어) if
  • literals 리터럴 "apple", 13
  • special symbols 특수 기호 ;, +, <=
  • identifiers  식별자(클래스 이름 등) IF
  • comments 주석(종종 공백으로 처리됨) /*abcde*/
    
    • 주석은 중첩이 불가능 not nested
• 주로 부과되는 식별자의 유효 문자 수
  • 언어가 아닌
  • 그러나 구현에 의해

어휘 구조 문제 Lexical Structure Issues

• 프로그램 레이아웃
  • 자유 형식(최근 트렌드)
  • 고정 형식
• 공백 무시 여부
  • DO 99 I = 1,10 -> For (I=1; I<=10; I++)
  • DO 99 I = 1.10 -> DO99I = 1.1;
• 키워드 예약 여부
  • 일부 언어의 키워드는 예약되어 있지 않습니다
  • FORTRAN은 이러한 언어의 예입니다.
    • IF(IF.LT.0) IF = IF + 1 ->첫번째는 식별자, 2~4번째는변수;;;
    • ELSE IF = IF + 2

정규식 Regular Expressions

• 토큰은 정규 표현식으로 공식적으로 설명할 수 있습니다.
  • Concatenation 연결: 항목의 순서를 지정하여 수행
  • Repetition 반복: 반복할 항목 뒤에 별표로 표시
  • Choice, or selection 선택 : 선택할 항목 사이에 세로 막대로 표시
• [ ] 하이픈이 있는 문자 범위를 나타냅니다.
• ? 선택 항목을 나타냅니다
• 마침표는 모든 문자를 나타냅니다.
• 예
  • 하나 이상의 숫자의 정수 상수
  • [0-9]+ , 543...
  • 부호 없는 부동 소수점(floating-point) 리터럴
  • [0-9]+(\.[0-9]+)?

스캐너

• 토큰 인식 프로그램
  • 스캐너: 토큰을 인식하는 프로그램을 스캔하여 순차적으로 반환하는 프로그램
  • 스캐너 구성 도구: 정규 표현식으로 작성된 주어진 스캐너 사양에 대한 스캐너를 빌드합니다. (lex 등)
• 간단한 스캐너 입력:
  

  • 

• 다음 출력을 생성합니다.

  • 

문맥 없는 문법

• BNF 예제(간단한 영어 문장의 경우, 순서대로 실행됨)
  • (1) sentence 문장 → 명사구 동사구 .
  • (2) noun-phrase 명사구 → 관사 명사
  • (3) article 관사 → a | NS
  • (4) noun 명사 → 소녀 | 개
  • (5) verb-phrase 동사구 → 동사 명사구
  • (6) verb 동사 → 보다 | 애완 동물
• 용어
  • 문법: 다시 쓰기 규칙의 집합(메타기호: →, |)
  • nonterminals: 화살표의 LHS(기사)
  • 터미널: 토큰(.)
  • 시작 기호: 지정된 비단말, 종종 첫 번째 규칙(문장)의 LHS

CFG는 "언어"를 생성합니다.

• 언어
  • 언어: 문장의 집합
  • 문장: 터미널의 연속
• Derivation 유도
  • 시작 기호부터 다시 쓰기 시퀀스
  • CFG에서 설명하는 언어는 파생어로 정의됩니다.
• 파생 예
  • 문장
    • Þ noun-phrase verb-phrase .
    • Þ article noun verb-phrase .
    • Þ the noun verb-phrase .
    • Þ the girl verb-phrase .
    • Þ the girl verb noun-phrase 
    • Þ the girl sees noun-phrase .
    • Þ the girl sees article noun .
    • Þ the girl sees a noun .
    • Þ the girl sees a dog .

      ---

• •  

• •  

• 문맥 없는 문법 재검토
• 문법 언어: 문맥 자유 문법으로 정의
• 비터미널이 프로덕션의 왼쪽에 단독으로 나타날 때 문법은 컨텍스트가 없습니다.
• 특정 교체만 발생할 수 있는 컨텍스트가 없습니다.
•  
• 문맥 자유 문법을 사용하여 표현할 수 없는 모든 것은 구문이 아니라 의미론적 문제입니다.
• BNF 형식의 언어 구문을 사용하면 번역기를 더 쉽게 작성할 수 있습니다.
• 구문 분석 단계를 자동화할 수 있습니다.
• CFG는 재귀적일 수 있습니다.
• 단순 반복
• 숫자 → 숫자 자리
• | 숫자
• 숫자 → 0 | 1 | 2 | 3 | 4
• | 5 | 6 | 7 | 8 | 9
•  
• 파생 예
• 숫자  숫자 자리
•  숫자 자릿수
•  자릿수 자릿수
•  2자리 숫자
•  23자리
•  234
• 구조 반복
• 특급 → 특급 + 특급
• | 특급 * 특급
• | (특급) | 숫자
• NUMBER = [0-9]+
•  
• 파생 예
• expr  expr * expr
•  ( expr )* expr
•  ( expr + expr ) * expr
•  ...  (2 + 3) * 4
•  
• 파스 트리
• 이론적 해석
• 많은 파생어가 문장의 동일한 구조를 나타낼 수 있음
• 숫자  숫자 자릿수  자릿수  자릿수 3  23
• 숫자  숫자 자릿수  자릿수  2자리  23
•  
• 파스 트리
• 파생물에 대한 그래픽 설명
• 구문 분석 트리에 대한 몇 가지 참고 사항
• 파스 트리의 해부
• 내부 노드는 비터미널에 해당합니다.
• 리프 노드는 터미널에 해당합니다.
• 루트 노드는 시작 기호에 해당합니다.
• A → xyz…와 같은 문법 규칙은 구문 분석 트리에서 한 수준을 생성합니다.
• 추상 구문 트리
• 이론적 해석
• 구문 분석 트리의 모든 정보가 번역에 필요한 것은 아닙니다.
•  
• 추상 구문 트리(AST)
• 압축된 파스 트리
• 비터미널 노드가 제거되고 일부 터미널 노드가 내부 노드가 됩니다.
• 구문 분석 트리 및 AST의 예
• 모호
• 모호한 문법
• 문장에 문법 규칙에 따라 두 개 이상의 파스 트리(또는 AST)가 있는 경우 grammar는 모호하다고 합니다.
• 모호성은 일부 문장의 구조가 고유하지 않음을 의미합니다.
•  
• 모호성 다루기
• 의미 체계는 어떤 구문 분석 트리가 올바른지 결정하는 데 도움이 됩니다.
• 종종 문법은 올바른 선택을 하기 위해 다시 작성될 수 있습니다.
• 모호성의 예
• 문법:
• 특급 → 특급 + 특급 | 특급 * 특급 | (특급) | 숫자
•  
• 문장: 3 + 4 * 5
•  
• 파싱 ​​트리:
•  
• 모호성의 또 다른 예
• 문법:
• 특급 → 특급 + 특급 | 특급 - 특급 | (특급) | 숫자
•  
• 문장: 3 - 4 - 5
•  
• 파싱 ​​트리:
•  
• 인상적인 연관성
• 비터미널의 재귀를 제어하여 연관성을 부과할 수 있습니다.
•  
• 왼쪽 결합성 부과
• 특급 → 특급 + 기간 | 특급 기간 | 기간
• 기간 → ( 특급 ) | 숫자
•  
• 우선 순위 부여
• 연산자의 우선 순위는 유사한 방법("우선 순위 캐스케이드")을 사용하여 부과할 수 있습니다.
•  
• +보다 *를 우선 적용
• 특급 → 특급 + 기간 | 기간
• 항 → 항 * 요인 | 요인
• 요인 → ( expr ) | 숫자
•  
• 문의는 없나요?
• 예, 하지만 둘 다 언어를 변경합니다.
•  
• 괄호로 묶인 표현식: expr ® ( expr + expr ) | ( 특급 * 특급 ) | 숫자: ((3 + 4) * 5) 및: (3 + (4 * 5))
•  
• 접두어 표현식: expr ® + expr expr | * 특급 특급 | 숫자: + + 3 4 5 및: + 3 * 4 5
• Scheme은 접두어를 사용하고 있습니까?
• Scheme은 산술 연산자에 여러 인수를 허용합니다. expr ® (op exprlist )| NUMBER개의 exprlist ® exprlist expr | 빈 빈 ®
• so: (+), (+ 1), (+ 1 2 3 4) 등 [- 및 /는 하나 이상의 인수가 필요합니다.]
• 단항 빼기
• 단항 - (부정)를 추가하여 각 표현식에 최대 하나의 단항 마이너스가 허용되고 표현식의 시작 부분에 와야 합니다.
• -3 + 4는 합법입니다(1과 같음). -3 + (-4)는 합법입니다. -3 + -4는 합법이 아닙니다.
•  
• 답: expr ® expr + term | 기간 | - 기간
• 확장 BNF
• 추가 메타심볼
• [ ] 선택적 구조의 경우
• 전:
• 반복 구조의 경우 { }
• 전:
•  
• 표현력
• 메타 심볼이 추가되어도 EBNF의 표현력은 BNF와 동일합니다.
• EBNF 예
• 되풀이
• BNF: expr → expr + term | 기간
• EBNF: expr → term { + term }
•  
• 선택 과목
• BNF: if-stmt → if ( expr ) stmt | if (expr) stmt else stmt
• EBNF: if-stmt → if ( expr ) stmt [ else stmt ]
• 구문 다이어그램
• EBNF에 기반한 대체 표기법
•  
• 전설
• 터미널용 타원형
• 비터미널용 직사각형
• 시퀀싱용 화살표
•  
• 노트
• 초보자도 이해하기 쉬운
• 더 이상 볼 수 없음: EBNF가 더 컴팩트함
• 구문 다이어그램 예
• 되풀이
• EBNF: expr → term { + term }
•  
•  
•  
•  
• 선택 과목
• EBNF: if-stmt → if ( expr ) stmt [ else stmt ]
•  
• 파싱
• "파싱"이란 무엇입니까?
• 프로그램 구문 분석
• 프로그램의 구문 트리 구성
• 파싱 ​​카테고리
• 하향식 구문 분석: 재귀 하강 구문 분석, LL 구문 분석
• 들어오는 토큰과 일치하도록 비터미널을 확장하고 파생물을 직접 구성합니다.
• 상향식 파싱: shift-reduce 파싱
• 입력을 규칙의 오른쪽과 일치시키고 왼쪽의 비터미널로 줄입니다(문자열을 비터미널로 줄이기 전에 토큰을 스택으로 이동)
• 파서 생성기
• 파서 설명에서 파서를 생성하기 위한 도구
• YACC, 들소, …
• 재귀 하강 파서 (1)
• 비터미널을 BNF의 우변을 기반으로 하는 상호 재귀적 절차 그룹으로 바꿉니다.
• 토큰은 스캐너에 의해 구성된 입력 토큰과 직접 일치합니다.
• 비 터미널은 비 터미널에 해당하는 절차에 대한 호출로 해석됩니다.
•  
• 재귀 하강 파서 (2)
• 왼쪽 재귀 규칙이 문제를 일으킬 수 있음
• 예시:
• 무한 재귀 루프를 일으킬 수 있음
• +가 표시될 때까지 두 가지 선택 중 어느 것을 선택할지 결정할 방법이 없습니다.
• EBNF 설명은 재귀를 루프로 표현합니다.
•  
• EBNF의 중괄호는 루프를 사용하여 왼쪽 재귀 제거를 나타냅니다.
•  
• 다음과 같은 오른쪽 재귀 규칙에 대한 코드:
•  
• 이것은 EBNF의 대괄호 사용에 해당합니다.
•  
• 이 프로세스를 레프트 팩터링이라고 합니다.
• 왼쪽 재귀 및 왼쪽 인수분해 상황 모두에서 EBNF 규칙 또는 구문 다이어그램은 자연스럽게 재귀-하강 파서의 코드에 해당합니다.
• 재귀 하강 예제
• 문법 expr → term { + term } term → factor { * factor } factor → ( expr ) | 숫자
•  
• 코드 스케치
•  
• 구문 분석 문제
• 단일 기호 예측: 단일 토큰을 사용하여 구문 분석 지시
•  
• 예측 파서: 미리보기만을 기반으로 특정 작업을 수행하는 파서
•  
• 이 의사결정 과정이 작동하려면 문법이 특정 조건을 충족해야 합니다.
• 파서는 규칙에서 선택 사항을 구별할 수 있어야 합니다.
• 선택적 부분의 경우 선택적 부분을 시작하는 토큰은 선택적 부분 뒤에 올 수 없습니다.
• 스캐너/파서 생성기
• 컴파일러 구성 도구
• 스캐너 생성기는 주어진 정규식 사양 파일에서 스캐너 코드를 생성합니다.
• 파서 생성기는 주어진 문법 사양 파일에서 파서 코드를 생성합니다.
•  
• 대표적인 예
• Unix 도구 Lex(Lesk, 1975) 및 YACC(Johnson, 1975)가 가장 널리 사용됩니다.
• 최신 무료 버전은 Gnu Bison 및 Flex("Fast lex")입니다.
•  
• 자세한 내용은 컴파일러 구성 과정에서 처리됩니다.
• 어휘 대 구문 대 Se맨틱
• 어휘와 구문 사이에 명확한 구분이 없습니다.
• 토큰 구조는 문법에 의해 지정될 수 있습니다.
• 일반적으로 특정 구현이 이 결정을 내립니다.
• 일부 규칙은 컨텍스트에 따라 달라지며 컨텍스트 없는 규칙으로 작성할 수 없습니다.
• 변수 사용 전 선언
• 프로시저 내에서 식별자 재선언 없음
• 이것은 언어의 의미론적 속성입니다.
•  
• 미리 정의된 식별자와 예약어 사이에 또 ​​다른 충돌이 발생합니다.
• 예약어는 식별자로 사용할 수 없습니다.
• 미리 정의된 식별자는 프로그램에서 재정의할 수 있습니다.
• 구문과 의미는 모호한 구문 분석 상황을 구별하기 위해 의미 정보가 필요할 때 상호 의존적일 수 있습니다.
•  
• 사례 연구: TinyAda용 구문 분석기
• TinyAda: 많은 고급 언어의 구문적 특징을 보여주는 작은 언어
• 여러 종류의 선언, 문 및 표현식 포함
• 선언, 명령문 및 표현식에 대한 규칙은 간접적으로 재귀적이며 중첩 선언, 명령문 및 표현식에 허용됩니다.
• Parsing shell: 문법 규칙을 적용하여 토큰이 올바른 유형인지 확인합니다.
• 수업 과정
• PL의 추석은 다녀왔습니다. 의정서에 대해 설명합니다.
• 6.12: BNF와 EBNF를 활용해서 작성하기
• 6.14: 구문 분석 트리와 추상 구문 트리의 이해
• 6.42: 파서까지 총정리