맨위로가기

Yacc

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

Yacc은 1970년대 초 스티븐 C. 존슨이 개발한 컴파일러 컴파일러로, BNF와 유사한 구문 규칙을 입력받아 구문 분석기를 자동으로 생성한다. 원래 B 언어로 작성되었으나 C 언어로 재작성되었으며, 유닉스 시스템에서 널리 사용되었다. Yacc은 Lex와 함께 사용되어 어휘 분석과 구문 분석을 수행하며, C++ 및 다양한 프로그래밍 언어의 파서 구현에 영향을 미쳤다. 현재는 GNU Bison, 버클리 Yacc 등의 대체 도구들이 사용되고 있으며, 컴파일러 개발, 설정 파일 분석 등에 활용된다.

더 읽어볼만한 페이지

  • 구문 분석기 - ANTLR
    ANTLR은 EBNF로 표현된 문법을 입력받아 렉서, 파서, 트리 파서 등 다양한 언어 인식기 소스 코드를 생성하는 파서 생성기이며, C#, Java, Python 등 여러 언어를 지원하고 깃허브에 다양한 문법이 공개되어 있다.
  • 구문 분석기 - GNU bison
    GNU Bison은 Yacc와 호환되면서 재진입성, 다양한 언어 코드 생성, 자동 반례 생성 등의 기능을 제공하는 파서 생성기로, 여러 프로젝트에서 Yacc를 대체하여 널리 사용되고 있으며, Bison으로 생성된 코드는 GPL과 호환되는 라이선스로 배포 가능하다.
  • 컴파일러 - 바이너리 재컴파일러
  • 컴파일러 - 링커 (컴퓨팅)
    링커는 여러 모듈로 된 목적 파일을 결합해 실행 가능한 프로그램을 만들고, 정적/동적 링킹으로 라이브러리를 연결하며, 심볼 해결 및 재배치로 변수와 함수를 메모리 주소에 연결하는 소프트웨어 도구이다.
Yacc - [IT 관련 정보]에 관한 문서
기본 정보
Yacc 로고
Yacc 로고
유형파서 생성기
개발자스티븐 C. 존슨
최초 릴리스1975년
최신 안정화 버전알 수 없음
프로그래밍 언어C
운영 체제유닉스
유닉스 계열
플랜 9
인페르노
플랫폼크로스 플랫폼
장르명령어
라이선스플랜 9: MIT 라이선스
웹사이트벨 연구소
명칭
풀이Yet Another Compiler Compiler (또 다른 컴파일러 컴파일러)
역사
개발1970년대 초, 스티븐 C. 존슨이 벨 연구소에서 개발
기술적 특징
기능LALR 파서 생성
구문 분석 규칙 정의
입력 파일`.y` 확장자를 가지는 문법 파일
출력 파일C 언어 소스 코드 (파서 구현)
활용
사용 분야컴파일러
인터프리터
데이터베이스 언어
텍스트 처리 도구
파생 및 유사 도구
종류Bison (GNU 프로젝트)
Flex (렉시컬 분석기, Yacc와 함께 사용)
BYacc
Mlyacc (OCaml 용)
ANTLR
Coco/R

2. 역사

1970년대 초, 벨 연구소의 컴퓨터 과학자 스티븐 C. 존슨은 B 언어 컴파일러 개발 과정에서 Yacc을 개발했다. Yacc은 LR 파싱에 관한 도널드 커누스의 연구와 더글러스 맥킬로이의 TMG 컴파일러-컴파일러[7]의 영향을 받았다.[9] Yacc은 원래 B 프로그래밍 언어로 작성되었지만, 곧 앨런 스나이더에 의해 C로 다시 작성되었다.[7] Version 3 Unix의 일부로 등장했으며,[8] 1975년에 전체 설명이 발표되었다.[9]

존슨은 Yacc을 사용하여 Portable C Compiler를 만들었으며,[8] 비야네 스트롭스트루프는 Yacc을 사용하여 C++의 첫 구현인 Cfront를 구현했다.[11] 2008년 인터뷰에서 존슨은 "Yacc이 유닉스와 C의 보급에 기여한 것이 가장 자랑스럽다"고 회고했다.[12]

2. 1. 개발 배경

1970년대 초, 벨 연구소의 컴퓨터 과학자 스티븐 C. 존슨은 B 언어 컴파일러[4]에 배타적 논리합 연산자를 추가하려다 어려운 문제에 직면하여 Yacc을 개발했다. 그는 알 아호의 지시로 LR 파싱에 관한 도널드 커누스의 연구를 참고했고, 이는 Yacc의 기반이 되었다.[5] Yacc은 더글러스 맥킬로이의 TMG 컴파일러-컴파일러의 영향을 받아[9] 이름이 지어졌다.[6]

2. 2. 초기 개발 및 발전

1970년대 초, 벨 연구소의 컴퓨터 과학자 스티븐 C. 존슨은 B 언어 컴파일러[4]에 배타적 논리합 연산자를 삽입하려다 어려운 문제에 직면하여 Yacc을 개발했다. 그는 알 아호의 지시로 LR 파싱에 관한 도널드 커누스의 연구를 접하게 되었고, 이는 Yacc의 기반이 되었다.[5] Yacc은 더글러스 맥킬로이의 TMG 컴파일러-컴파일러의 영향을 받아[7] 이름을 따왔다.[6]

Yacc은 원래 B 프로그래밍 언어로 작성되었지만, 곧 앨런 스나이더가 C로 다시 작성했다.[7] Version 3 Unix의 일부로 처음 등장했으며,[8] 1975년에 전체 설명이 발표되었다.[9]

존슨은 Yacc을 사용하여 Portable C Compiler를 만들었다.[8] 비야네 스트롭스트루프는 Yacc을 사용하여 C++의 공식 사양을 만들려고 시도했지만, "C의 구문에 의해 실패했다."[10] 그는 언어의 공식 사양에는 적합하지 않다고 판단했지만, Yacc을 사용하여 C++의 첫 번째 구현인 Cfront를 구현했다.[11]

2008년 인터뷰에서 존슨은 "Yacc이 유닉스와 C의 보급에 기여한 것이 가장 자랑스럽다"고 회고했다.[12]

Yacc는 yet another compiler compiler영어 (또 하나의 컴파일러 컴파일러)에서 유래했다. 컴퓨터 초창기에는 프로그래밍 언어 처리계 기술의 발전 방향으로, 당시 기계어 프로그램을 생성하는 컴파일러 다음은 컴파일러를 생성하는 컴파일러 컴파일러일 것이라는 생각에 연구가 활발히 진행되었고, 이 때문에 컴파일러 컴파일러를 자칭하는 연구가 여럿 존재했다.

파서가 컴파일러의 전부는 아니므로, 컴파일러 컴파일러라고 부르기에는 Yacc와 같은 파서 생성기는 부족하다고 볼 수도 있지만, 특별히 의식되는 경우는 적다.

2. 3. C++와 Yacc

비야네 스트롭스트루프는 Yacc를 사용하여 C++의 공식 사양을 만들려고 시도했지만, C 언어 구문의 복잡성으로 인해 실패했다.[10] 하지만 스트롭스트루프는 Yacc를 사용하여 C++의 초기 구현인 Cfront를 개발했다.[11]

3. 설명

Yacc는 입력으로 규칙에 C 코드 조각( "액션"이라고 함)이 첨부된 문법을 받는다. Yacc의 출력은 규칙이 인식될 때마다 해당 C 코드 조각을 실행하는 C 언어 시프트-감소 파서이다. 일반적인 액션에는 파스 트리 구성이 포함된다.[9]

Yacc는 스캐너리스 파싱에서 단독으로 사용할 수 있는 파서(구문 분석기)만 생성하지만, 완전한 구문 분석을 위해서는 보통 토큰화 단계를 위한 외부 어휘 분석기가 필요하다. 그 후 파싱 단계가 이어진다.[9] Lex나 Flex 같은 어휘 분석기 생성기가 널리 사용된다. IEEE POSIX P1003.2 표준은 Lex와 Yacc의 기능 및 요구 사항을 정의한다.[13]

AT&T Yacc의 일부 버전은 오픈 소스 소프트웨어가 되었다. 예를 들어 플랜 9 표준 배포판에서 소스 코드를 사용할 수 있다.[14]

3. 1. 입력 및 출력

Yacc의 입력은 규칙에 첨부된 C 코드 조각("액션"이라고 함)이 있는 문법이다. Yacc의 출력은 규칙이 인식되는 즉시 각 규칙과 관련된 C 코드 조각을 실행하는 C 언어로 작성된 시프트-감소 파서이다. 일반적인 액션에는 파스 트리의 구성이 포함된다.[9] 예를 들어, `node(label, left, right)`가 지정된 `label`과 자식 노드를 가진 이진 파스 트리 노드를 구성하는 경우, 다음 규칙은

```c

expr : expr '+' expr { $$ = node('+', $1, $3); }

```

합산 표현식을 인식하고 이에 대한 노드를 구성한다. 특수 식별자 `$$`, `$1` 및 `$3`는 파서의 스택의 항목을 나타낸다.[9]

Yacc는 스캐너리스 파싱의 경우 단독으로 사용할 수 있는 파서(구문 분석기)만 생성하지만, 완전한 구문 분석에는 일반적으로 토큰화 단계를 먼저 수행하기 위해 외부 어휘 분석기가 필요하며, 이어서 파싱 단계가 진행된다.[9] 이러한 목적으로 Lex 또는 Flex와 같은 어휘 분석기 생성기가 널리 사용된다. IEEE POSIX P1003.2 표준은 Lex와 Yacc의 기능 및 요구 사항을 정의한다.[13]

Yacc는 고전적인 컴파일러 컴파일러이지만, 산업용 및 교육용으로 널리 사용된다. 컴파일러 개발뿐만 아니라, 고유한 설정 파일 분석, 프로그래밍 언어 변환기 개발, 간이 계산기 예제 학습 등에도 사용된다.

Yacc는 대부분의 UNIX 시스템에서 기본 파서 생성기로 사용 가능했다. Yacc와 상위 호환성을 가진 소프트웨어로는 GNU 프로젝트의 Bison, [http://invisible-island.net/byacc/byacc.html Barkeley Yacc（byacc）], [http://byaccj.sourceforge.net/ BYACC/J], [http://www.mkssoftware.com/products/ly/ MKS Yacc], Abraxas pcyacc 등이 있다.

또한 Yacc는 Java, Ratfor, EFL, ML, Ada, Limbo 등 다른 언어를 생성하는 버전으로도 이식되었다.

Java용으로는 Yacc와 유사한 LALR 방식의 [http://web.cecs.pdx.edu/~mpj/jacc/ jacc], [http://www2.cs.tum.edu/projects/cup/ CUP] (JavaCUP), [http://sablecc.org/ SableCC], [http://www.informatik.uni-osnabrueck.de/alumni/bernd/jay/ jay] 등이 있으며, Yacc와 다른 방식으로는 LL(k) 방식의 JavaCC와 Coco/R, LL(*) 방식의 [http://www.antlr.org/ ANTLR]가 있다.[30]

Yacc를 이용하여 컴파일러를 개발하는 경우에는 코드 생성부에 넘겨줄 추상 구문 트리(AST)라는 데이터 구조를 구축해야 한다. 예를 들어, 액션에서 사용자 정의 함수를 호출하여

```c

{ $$ = node( '+', $1, $3 ); }

```

와 같이 좌변과 우변을 "+"로 결합하여 그 포인터를 반환하는 방식으로 수행할 수 있다. 그러면 구문 분석이 말단에서부터 순차적으로 환원되어 뿌리까지 통합되었을 때, 추상 구문 트리가 완성된다.

이처럼 잎에서부터 순서대로 뿌리에 이르는 구문 분석법을 바텀업 구문 분석이라고 한다.

3. 2. 어휘 분석기와의 관계

Yacc는 파서(구문 분석기)만 생성하므로, 완전한 구문 분석을 위해서는 토큰화 단계를 먼저 수행하기 위해 외부 어휘 분석기가 필요하다.[9] Lex나 Flex와 같은 어휘 분석기 생성기가 Yacc와 함께 널리 사용된다. IEEE POSIX P1003.2 표준은 Lex와 Yacc의 기능 및 요구 사항을 정의한다.[13]

Yacc는 구문 분석기 기능만 있지만, `yylex`라는 이름의 미구현 함수를 호출하여 매번 토큰을 요구한다. 사용자는 이 어휘 분석기 함수 `yylex`를 만들어 동적으로 토큰을 생성하고, 한 번 호출될 때마다 하나의 토큰 종류를 반환해야 한다. 숫자나 문자열처럼 의미 값을 갖는 토큰일 때는, 의미 값도 변수 `yylval`에 설정하여 반환한다.[25]

어휘 분석기 쪽도 합리적인 개발을 위해 Yacc와 유사한 규칙 정의를 제공하는 Lex[26]나 Flex[27] 등의 렉시컬 애널라이저 제너레이터를 사용해 어휘 분석기를 자동 생성할 수 있다.

Lex 등의 어휘 분석기 생성 툴을 이용하면, 어휘 문법 정의를 통해 생성된 C 언어 소스인 어휘 분석기가 `yylex` 함수를 포함하므로, C 컴파일로 Yacc 출력과 함께 링크하여 통합한다. 이로써 소스 텍스트의 어휘 분석과 구문 분석을 모두 수행하고, 규칙의 액션부 (또는 호출되는 사용자 작성 C 언어 함수)에 쓰여진 계산 결과, 컴파일 생성에 사용되는 추상 구문 트리 구조체 데이터, 각종 표시 등이 출력되는 변환 프로그램이 완성된다. GNU 프로젝트에서는 Flex라는 이름으로 기능을 제공한다.

Yacc와 Lex는 매우 유사한 문법 정의를 가지며, 함께 사용하고 설명하는 경우가 많다. Lex와 Yacc의 기능은 IEEE POSIX 1003.1-2008 (이전에는 1003.2)에서 표준화하고 있다.[29]

4. 기능 개요

Yacc는 주어진 문법 규칙을 바탕으로 구문 분석기를 자동으로 생성하는 도구이다. Yacc가 생성하는 구문 분석기는 입력된 내용을 토큰 단위로 처리하며, 이를 위해 어휘 분석 과정이 필요하다.

Yacc는 컴파일러에서 구문 분석을 담당한다. 컴파일러는 소스 코드를 기계가 이해할 수 있는 코드로 변환하는데, 이때 소스 코드를 의미 있는 단위인 토큰으로 나누는 어휘 분석기와 이 토큰들을 분석하여 구문 트리를 생성하는 구문 분석기로 구성된다. Yacc는 이러한 구문 분석기를 자동으로 생성해준다.

Yacc는 숫자, 영문자, 공백 등을 1글자 단위로 분석하지 않고, "print" 같은 단어, "1999" 같은 숫자, "++" 같은 연산자처럼 토큰(token) 단위를 사용한다.[30]

Yacc는 토큰을 얻기 위해 `yylex()` 함수를 호출한다. `yylex()` 함수는 토큰의 종류와 의미 값을 반환하며, 파일 끝에 도달하면 0 또는 음수를 반환한다. 사용자는 `yylex()` 함수를 직접 작성하거나, Lex, Flex 등의 어휘 분석기 생성 도구를 사용할 수 있다.[30]

예를 들어, 계산기 프로그램에서 "10+20*30-40"을 입력하면, `yylex()` 함수는 Yacc에 다음과 같은 토큰들을 반환한다.


  • NUM (의미 값: 10)
  • '+'
  • NUM (의미 값: 20)
  • '*'
  • NUM (의미 값: 30)
  • '-'
  • NUM (의미 값: 40)
  • EOL (줄바꿈)
  • 0 (파일 끝)

4. 1. 파서 생성 방식

Yacc는 BNF과 유사한 구문 규칙을 입력으로 받아 구문 분석기를 자동 생성한다. 생성되는 구문 분석기는 분석 테이블과 이를 사용하는 프로그램으로 구성된다. 구문 분석 기법은 LALR 파싱이다.[30]

LALR 파싱은 상향식 구문 분석의 일종으로, LR 파싱에 제한을 가한 기법이다. 여기서 L은 입력을 왼쪽에서 읽는다는 것을, R은 오른쪽 가장자리 유도를 의미하며, 숫자 (1)은 미리 읽는 토큰 수가 1개임을 뜻한다. C 언어, Java영어 등 많은 프로그래밍 언어의 구문 분석기를 구현할 수 있을 만큼 강력하면서도, 분석 테이블이 간결하다는 장점이 있다.[30]

Yacc가 생성하는 구문 분석기는 내부적으로 스택을 가진 유한 상태 기계이다. 구문 분석기는 다음 토큰을 하나씩 읽어(선행 토큰, look-ahead token) 분석 테이블을 참조하여 다음과 같은 동작을 반복한다.[32]

  • 시프트(shift): 선행 토큰을 스택에 추가한다.
  • 환원(reduce): 스택의 오른쪽 끝에 있는 기호들을 특정 규칙에 따라 치환하고, 스택 크기를 줄인다.
  • 전이(goto): 생성된 비종단 기호를 shift한다.
  • 수락(accept): 구문 분석이 정상적으로 종료되었음을 의미한다.
  • 에러(error): 구문 분석 중 오류가 발생했음을 의미한다.


구문 분석기는 입력 토큰들을 스택에 넣고 규칙을 적용하며, 성공하면 환원하는 과정을 반복한다. 테이블에 따라 상태 전이를 하며, 최종적으로 입력 문자열이 문법에 맞는지 판단한다.[33]

4. 2. 토큰과 어휘 분석

Yacc는 숫자, 영문자, 공백 등을 1글자 단위로 분석하는 대신, 토큰(token) 단위를 사용한다. 예를 들어, "print" 같은 단어, "1999" 같은 숫자, "++" 같은 연산자를 토큰으로 인식한다.[30]
어휘 분석(lexical analyzer)은 소스 코드를 이러한 토큰들의 나열로 변환하는 역할을 한다. Yacc는 어휘 분석기 함수 `yylex`를 호출하여 토큰을 요구하며, `yylex`는 토큰의 종류와 의미 값을 반환한다.[30]

일반적으로 컴파일러에서 구문 분석부는 어휘 분석기(A-1)와 구문 분석기(A-2)로 나뉜다. 어휘 분석기는 소스 코드를 토큰열로 만들고, 구문 분석기는 이 토큰열을 바탕으로 구문 트리를 생성한다. Yacc는 이러한 구문 분석기를 자동으로 생성해주는 도구이다.

```

컴파일러

├구문 분석부(A)

│　├어휘 분석기(A-1)　←〔소스 코드〕（문자열）

│　│　　　↓

│　│　　〔토큰열〕

│　│　　　↓

│　└구문 분석기(A-2)

│　　　　　↓

│　　〔구문 트리〕

│　　　　　↓

└코드 생성부(B)　　　→〔목표 코드〕

```

Yacc는 `yylex()` 함수를 호출하여 토큰을 입력받는다. `yylex()` 함수는 토큰의 종류와 의미 값을 반환하며, 파일의 끝에 도달하면 0 또는 음수를 반환한다. 사용자는 `yylex()` 함수를 직접 작성하거나, Lex, Flex 등의 어휘 분석기 생성 도구를 사용할 수 있다.[30]

예를 들어, 계산기 프로그램에서 "10+20*30-40"을 입력하면, `yylex()` 함수는 Yacc에 다음과 같은 토큰들을 반환한다.

  • NUM (의미 값: 10)
  • '+'
  • NUM (의미 값: 20)
  • '*'
  • NUM (의미 값: 30)
  • '-'
  • NUM (의미 값: 40)
  • EOL (줄바꿈)
  • 0 (파일 끝)


Yacc는 이러한 토큰들을 바탕으로 구문 규칙에 따라 계산을 수행하고 결과를 출력한다.

5. 영향 및 파생 도구

Yacc는 다양한 프로그래밍 언어 구현에 영향을 주었으며, 여러 파생 도구들이 개발되었다.

Yacc는 벨 연구소 라이선스 하에 찰스 리버 데이터 시스템의 UNOS 운영 체제에서 사용할 수 있는 여러 유닉스 도구 중 하나였다.[16]

Yacc의 주요 파생 도구들은 다음과 같다:


  • 버클리 Yacc: 버클리에서 구현된 Yacc로, 성능이 좋고 재사용 제한이 없어 AT&T Yacc보다 빠르게 인기를 얻었다.[24]
  • LALR 파서: Yacc로 생성된 파서의 기본 파싱 알고리즘이다.
  • Bison: Yacc의 GNU 버전이다.
  • Lex (및 Flex lexical analyser): Yacc (및 Bison)과 함께 일반적으로 사용되는 토큰 파서이다.
  • BNF: 문맥 자유 문법을 표현하는 데 사용되는 메타구문으로, 문맥 자유 언어를 설명하는 형식적인 방법이다.
  • PLY (Python Lex-Yacc): Python에서 Lex와 Yacc를 대체하여 구현한 것이다.

5. 1. 인기 및 대체 도구

Yacc 및 유사한 프로그램(주로 재구현)은 매우 인기가 있었다. Yacc 자체는 대부분의 유닉스 시스템에서 기본 파서 생성기로 사용되었지만, 이후 버클리 Yacc, GNU Bison, MKS Yacc, Abraxas PCYACC와 같이 더 최근의, 대체로 호환되는 프로그램으로 대체되었다. 원래 AT&T Yacc의 업데이트된 버전은 썬의 OpenSolaris 프로젝트의 일부로 포함되어 있다. 각각은 원래 Yacc에 비해 약간의 개선과 추가 기능을 제공하지만, 개념과 기본 구문은 동일하게 유지되었다.[15]

Yacc는 또한 벨 연구소 라이선스 하에 찰스 리버 데이터 시스템의 UNOS 운영 체제에서 사용할 수 있는 여러 유닉스 도구 중 하나였다.[16]

Yacc로 처음 구현된 언어 중에는 AWK, C++,[17] eqn 및 Pic이 있다.[18] Yacc는 또한 유닉스에서 Portable C Compiler를 구현하는 데 사용되었으며, FORTRAN 77, Ratfor, APL, bc, m4 등과 같은 프로그래밍 언어의 파서를 구현하는 데에도 사용되었다.[8][19]

Yacc는 또한 OCaml,[20] Ratfor, ML, Ada, Pascal, Java, PHP, Python, Ruby, Go,[21] Common Lisp[22] 및 Erlang을 포함한 다른 언어로도 다시 작성되었다.[23]

  • 버클리 Yacc: 버클리에서 구현된 Yacc는 성능과 재사용 제한이 없다는 점 때문에 AT&T Yacc 자체보다 빠르게 더 인기를 얻었다.[24]
  • LALR 파서: Yacc로 생성된 파서의 기본 파싱 알고리즘.
  • Bison: Yacc의 GNU 버전.
  • Lex (및 Flex lexical analyser), Yacc (및 Bison)과 함께 일반적으로 사용되는 토큰 파서.
  • BNF는 문맥 자유 문법을 표현하는 데 사용되는 메타구문이다. 즉, 문맥 자유 언어를 설명하는 형식적인 방법이다.
  • PLY (Python Lex-Yacc)는 Python에서 Lex와 Yacc를 대체하여 구현한 것이다.

5. 2. 오픈 소스화

Yacc 및 유사한 프로그램(주로 재구현)은 매우 인기가 있었다. Yacc 자체는 대부분의 유닉스 시스템에서 기본 파서 생성기로 사용되었지만, 이후 버클리 Yacc, GNU Bison, MKS Yacc, Abraxas PCYACC와 같이 더 최근의, 대체로 호환되는 프로그램으로 대체되었다. 원래 AT&T Yacc의 업데이트된 버전은 썬의 OpenSolaris 프로젝트의 일부로 포함되어 있다.[15] 각각은 원래 Yacc에 비해 약간의 개선과 추가 기능을 제공하지만, 개념과 기본 구문은 동일하게 유지되었다.

5. 3. Yacc로 구현된 언어

Yacc는 AWK, C++, eqn, Pic 등 다양한 언어 구현에 사용되었다. 또한 유닉스에서 Portable C Compiler를 구현하는 데 사용되었으며, FORTRAN 77, Ratfor, APL, bc, m4 등과 같은 프로그래밍 언어의 파서를 구현하는 데에도 사용되었다.[8][19]

5. 4. 다른 언어로의 재작성

Yacc는 OCaml,[20] Ratfor, ML, Ada, Pascal, Java, PHP, Python, Ruby, Go,[21] Common Lisp,[22] Erlang을 포함한 다른 언어로도 다시 작성되었다.[23]

6. 기본 구성

Yacc의 기본 구성은 다음과 같다.

```

%{

(C 선언부: 헤더 파일의 인클루드 등 C 언어의 초기 설정)

%}

(Yacc 선언부: 토큰 및 우선순위 정의 등)

%union {

(토큰 및 그룹과 그 의미 값의 타입 정의)

}

%%

(문법 규칙부: 구문 규칙)

%%

(추가 C 프로그램부: 이하는 그대로 프로그램으로 출력된다)

```


  • C 선언부: 매크로 정의 및 문법 규칙의 액션 함수를 C 언어로 기술하는 부분이다. 구문 분석기 프로그램의 처음에 그대로 복사된다. 예를 들어 다음과 같다.


```c

#include

```

  • Yacc 선언부: 시작 기호 ("%start"), 값 유형 집합 ("%union"), 토큰(종단 기호) 선언 ("%token"), 그룹(비종단 기호) 선언 ("%type"), 연산자 우선순위 지정 ("%left", "%right", "%nonassoc") 등을 필요에 따라 기술하는 부분이다. 예를 들어 다음과 같다.


```c

%token NUM /* 토큰 (종단 기호)과 그 의미값 yylval의 유형 정의. */

```

Bison의 경우 Bison 선언부라고 부르며, 이 경우 충돌 경고 억제 ("%expect"), 순수 (재진입 가능) 구문 분석기 지정 ("%pure_parser")을 할 수 있다.

  • 문법 규칙부: 1개 이상의 Yacc 문법 규칙을 기술해야 한다.


```

변환 결과: 구성 요소 1 구성 요소 2 …

;

```

여기서 변환 결과는 규칙이 기술하는 비종단 기호이다. 구성 요소는 이 규칙이 일치하는지 판별하기 위해 문법에 따라 순서대로 정렬되는 0개 이상의 종단 기호나 비종단 기호의 열이다. 예를 들어 다음과 같다.

```c

qa: expr { printf(" Ans = %Lg", $1); prompt(); } /* 규칙 5 개행으로 계산, 표시. */

```

같은 변환 결과를 생성하는 여러 규칙은 다음과 같이 간략하게 연속 기술할 수 있다.

```

변환 결과: 구성 요소 11 구성 요소 12 …

| 구성 요소 21 구성 요소 22 …

| 구성 요소 31 구성 요소 32 …

;

```

";"는 생략 가능하다.

구문 규칙은 읽고 쓰기 쉬운 BNF 표기법으로 되어 있다.

규칙에 일치할 때마다 수행할 동작은 C 언어 명령에 의한 액션으로 "{ }"로 묶는다. 일치 직전에 실행하고 싶은 구성 요소 바로 앞에 붙이거나, 규칙 적용 시 실행으로 충분하다면 그 규칙의 마지막 구성 요소 뒤에 기술한다. 예를 들어 "{ printf(" Ans = %Lg", $1); prompt(); }"는 qa가 expr에 일치하는 것으로 판정되었을 때 실행된다.

규칙은 재귀적으로 정의할 수 있다.

6. 1. Yacc 문법 파일

사용자는 Yacc 문법 파일에 변환 사양을 텍스트 파일로 작성한다. Yacc 문법 파일은 C 선언부, Yacc 선언부, 문법 규칙부, 추가 C 프로그램부로 구성된다.[30]

  • C 선언부: 헤더 파일의 인클루드 등 C 언어의 초기 설정을 작성한다. 매크로 정의 및 문법 규칙의 액션 함수를 C 언어로 기술할 수 있으며, 구문 분석기 프로그램의 처음에 그대로 복사된다.[30]
  • Yacc 선언부: 토큰 및 우선순위 정의 등 Yacc 설정을 작성한다. 시작 기호 ("%start"), 값 유형 집합 ("%union"), 토큰(종단 기호) 선언 ("%token"), 그룹(비종단 기호) 선언 ("%type"), 연산자 우선순위 지정 ("%left", "%right", "%nonassoc") 등을 필요에 따라 기술할 수 있다.[30] Bison의 경우 Bison 선언부라고 부르며, 충돌 경고 억제 ("%expect"), 순수 (재진입 가능) 구문 분석기 지정 ("%pure_parser")을 할 수 있다.[30]
  • 문법 규칙부: 1개 이상의 Yacc 문법 규칙을 작성한다. 구문 규칙은 읽고 쓰기 쉬운 BNF 표기법으로 되어 있다.[30]
  • 추가 C 프로그램부: 함수, 변수 등을 C 언어로 기술하는 부분이다. 구문 분석기 프로그램에서 `yyparse()` 함수의 전개가 끝난 후의 말미에 그대로 복사된다. 예를 들어, 어휘 분석기 함수 `yylex()`, 오류 보고 함수 `yyerror()`, C 언어 메인 프로그램 `main()` 등도 각각 필요하다면 여기에 기술한다.[30]

6. 2. 입력, 출력 및 처리

`yacc` 명령어는 Yacc 문법 파일(`.y` 확장자)을 입력으로 받아 C 언어 소스 프로그램(`y.tab.c`)을 출력한다. 이 C 소스 프로그램에는 LALR 분석 테이블과 드라이버 루틴이 포함된다. 구문 분석 전체는 `yyparse()` 함수가 수행한다.

`-d` 옵션을 사용하면 헤더 파일(`y.tab.h`)이 생성되는데, 이는 Lex가 토큰 처리를 할 때 Yacc가 할당한 토큰 값을 올바르게 사용하기 위해 제공된다.

`-v` 옵션을 사용하면 분석 테이블 정보(문법, 종단/비종단 기호, 상태, 판정 패턴, 시프트/환원 조치, 상태 전이 등)를 사람이 읽기 쉬운 형태의 텍스트 파일(`y.output`)로 출력한다.

`-t` 옵션을 지정하면 생성된 파서 실행 시 상태 번호, 스택 상태, 읽은 토큰, 의미 값 연산 상태, 변화된 상태 번호 등이 표준 에러 출력에 표시되어 디버깅에 유용하다.

Yacc로 생성된 구문 분석기 소스 프로그램(`y.tab.c`)은 `cc`나 `gcc` 등으로 컴파일한다. Lex를 사용했다면 그 출력(`lex.yy.c`)도 함께 컴파일하고, 해당 라이브러리를 링크한다.

컴파일된 프로그램을 실행하면 표준 입력(또는 `yyin`으로 지정된 파일)을 읽어 어휘 분석기 함수 `yylex()`를 통해 토큰으로 만들고 구문 분석을 실행한다. 변환 결과나 에러는 Yacc 액션부나 호출되는 함수에서 작성한 처리에 따라 출력된다. 구문 오류는 `yyerror()` 함수를 통해 처리하며, 에러 메시지에 파일명, 행 번호, 토큰 번호 등을 추가하는 것이 좋다.

다음은 `bison` (Yacc 상위 호환)을 사용한 명령어 예시이다 (Windows Cygwin 환경).

```bash

> bison -ydv ./wiki_samp1.y

> gcc -DYYERROR_VERBOSE -DYYDEBUG ./y.tab.c -ly -lm -o wiki_samp1_parser > wiki_samp1_gcc_outlist.txt

> ./wiki_samp1_parser.exe < ./indata.txt

```

`bison -y`는 Yacc 호환 모드로 처리한다. `indata.txt`는 분석할 파일을 지정하며, `< indata.txt`를 생략하면 대화형으로 입력할 수 있다.

7. 동작 원리

Yacc가 생성하는 구문 분석기는 내부 스택을 가진 유한 상태 기계이다. 구문 분석기는 다음 토큰을 1개 읽어 변수 yychar에 넣고, 분석 테이블을 검색하여 규칙과의 일치를 조사한다. (오른쪽 끝 유도)[32]

구문 분석기는 종료 조건까지 다음 과정을 반복한다.


  • 현재 상태에서 선행(lookahead) 토큰이 필요하고, 현재 설정되어 있지 않으면 yylex()를 호출하여 선행 토큰을 받는다.
  • 현재 상태와 선행 토큰에 의해 결정되는 액션을 실행한다.


Yacc에 의해 분석 테이블에 전개되는 기계의 액션 종류는 다음과 같다.

  • 시프트(shift): 선행 토큰이 필요하며, 그것을 스택에 1개 추가(푸시)한다. 선행 토큰은 소비된다.
  • 환원(reduce): n번째 규칙의 오른쪽에 있는 기호군에서 왼쪽의 그룹(비종단 기호)으로 치환을 적용하여, 오른쪽 변에 해당하는 수만큼 스택 요소를 팝업한다. 스택의 크기는 줄어든다. 그리고 왼쪽 변인 그룹(비종단 기호)을 1개 다시 푸시한다. 이 그룹에 의미값이 있으면, 반환값에서 설정된다. 동시에 상태는 (현재 상태가 아니라) 스택의 맨 위(가장 오른쪽)에 있는 상태 번호로 된다. 환원을 기동하는 조건으로서 분석 테이블에 "."(버전에 따라서는 "$default")라고 써 있으면 무조건 실행되지만, "MINUS" 등과 같이 선행 토큰 값이 주어질 때는 그것이 일치할 때에 한해서 실행된다.
  • 전이(goto): 생성된 비종단 기호를 shift한다. 다음 종단 기호는 이 뒤의 shift에 맡겨진다. 선행 토큰은 소비되지 않는다.
  • 수락(accept): 구문 분석의 정상 종료이며, yyparse()에서 반환값 0으로 정상 복귀한다. 이 동작은 yylex()에서 0 또는 음수가 반환되어 다음 종단 기호가 끝을 의미하는 $end가 되었을 때, 규칙 0 "$accept: 전체의 비종단 기호명 $end"에 의해 스택이 올바르게 $accept의 1개로 환원될 수 있을 때 실행된다.
  • 에러(error): 분석표의 빈 칸, 즉 다음에 나타나서는 안 되는 종단 기호가 있을 때 매치되도록 전개된다. 구문 분석기는 에러를 검출하면, "error" 토큰이 정상적으로 일치하는 규칙을 찾을 때까지 스택을 팝업하면서 돌아간다. 찾으면 거기에 "error"라는 토큰이 있었다고 간주하여, 검출되는 규칙의 액션을 실행한다. 그리고 선행 토큰은 에러를 일으킨 토큰으로 진행한다(리셋). Yacc는 에러 다발 방지를 위해 토큰 3개의 읽기 및 시프트가 성공할 때까지 이 에러 상태에 머무르지만, 사용자가 액션에서 yyerrok(에러 회복) 매크로를 실행하면 그 도중에도 정상 상태로 돌아간다.[33]


가능한 환원은 여러 번 실행된 후에 토큰은 시프트된다.

구문 분석기는 입력된 토큰 열을 스택에 넣었다가 차례로 위와 같이 규칙 적용을 시도하고, 성공할 때마다 환원해 간다. 그리고 테이블의 지정에 따라 상태 전이해 간다.[34]

내부의 하위 비종단 항목(그룹)이 확정되면, 그 값이 그 비종단 항목에 해당하는 상위의 미확정된 오른편의 항에 대입되고, 그 왼쪽의 그룹이 스택에 푸시됨으로써, 점점 상위로 해결되어 간다.

토큰을 받은 상태 번호를 상태 스택에 넣었다 빼면 완전 동기화되어, (있으면) 그 토큰의 의미값도 의미값 스택에 넣었다 뺀다. 이것에 의해 액션에 의한 의미값 계산을 보증하고 있다.

최종 목표는 전부 읽었을 때, "%start"로 지정되어 분석을 시작한 비종단 기호(디폴트는 처음에 쓰여 있는 규칙의 왼편)가 변환의 결과 $accept 1개로 환원될 수 있었는지를 조사하는 것이다. 만약 그것이 되지 않았다면, 입력 문자열은 이 문법에 적합하지 않은 에러라는 것을 알 수 있다. 만약 가능했다면, 이 문법에 적합하다고 판단할 수 있으며, 그것에 직접 또는 재귀적으로 내포되는 모든 요소에 해당하는 입력 토큰 열이 확정된다.

7. 1. 파서의 내부 구조

Yacc가 생성하는 구문 분석기는 내부에 스택을 가진 유한 상태 기계이다. 구문 분석기는 다음 토큰을 1개 읽어 변수 yychar에 넣고, 분석 테이블을 검색하여 규칙과의 일치를 조사한다. (오른쪽 끝 유도)[32]

구문 분석기는 종료 조건까지 다음 과정을 반복한다.

  • 현재 상태에서 선행(lookahead) 토큰이 필요하고, 현재 설정되어 있지 않으면 yylex()를 호출하여 선행 토큰을 받는다.
  • 현재 상태와 선행 토큰에 의해 결정되는 액션을 실행한다.


Yacc에 의해 분석 테이블에 전개되는 기계의 액션 종류는 다음과 같다.

  • 시프트(shift): 선행 토큰이 필요하며, 그것을 스택에 1개 추가(푸시)한다. 선행 토큰은 소비된다.
  • 환원(reduce): n번째 규칙의 오른쪽에 있는 기호군에서 왼쪽의 그룹(비종단 기호)으로 치환을 적용하여, 오른쪽 변에 해당하는 수만큼 스택 요소를 팝업한다. 스택의 크기는 줄어든다. 그리고 왼쪽 변인 그룹(비종단 기호)을 1개 다시 푸시한다. 이 그룹에 의미값이 있으면, 반환값에서 설정된다. 동시에 상태는 (현재 상태가 아니라) 스택의 맨 위(가장 오른쪽)에 있는 상태 번호로 된다. 환원을 기동하는 조건으로서 분석 테이블에 "."(버전에 따라서는 "$default")라고 써 있으면 무조건 실행되지만, "MINUS" 등과 같이 선행 토큰 값이 주어질 때는 그것이 일치할 때에 한해서 실행된다.
  • 전이(goto): 생성된 비종단 기호를 shift한다. 다음 종단 기호는 이 뒤의 shift에 맡겨진다. 선행 토큰은 소비되지 않는다.
  • 수락(accept): 구문 분석의 정상 종료이며, yyparse()에서 반환값 0으로 정상 복귀한다. 이 동작은 yylex()에서 0 또는 음수가 반환되어 다음 종단 기호가 끝을 의미하는 $end가 되었을 때, 규칙 0 "$accept: 전체의 비종단 기호명 $end"에 의해 스택이 올바르게 $accept의 1개로 환원될 수 있을 때 실행된다.
  • 에러(error): 분석표의 빈 칸, 즉 다음에 나타나서는 안 되는 종단 기호가 있을 때 매치되도록 전개된다. 구문 분석기는 에러를 검출하면, "error" 토큰이 정상적으로 일치하는 규칙을 찾을 때까지 스택을 팝업하면서 돌아간다. 찾으면 거기에 "error"라는 토큰이 있었다고 간주하여, 검출되는 규칙의 액션을 실행한다. 그리고 선행 토큰은 에러를 일으킨 토큰으로 진행한다(리셋). Yacc는 에러 다발 방지를 위해 토큰 3개의 읽기 및 시프트가 성공할 때까지 이 에러 상태에 머무르지만, 사용자가 액션에서 yyerrok(에러 회복) 매크로를 실행하면 그 도중에도 정상 상태로 돌아간다.[33]


가능한 환원은 여러 번 실행된 후에 토큰은 시프트된다.

구문 분석기는 입력된 토큰 열을 스택에 넣었다가 차례로 위와 같이 규칙 적용을 시도하고, 성공할 때마다 환원해 간다. 그리고 테이블의 지정에 따라 상태 전이해 간다.[34]

내부의 하위 비종단 항목(그룹)이 확정되면, 그 값이 그 비종단 항목에 해당하는 상위의 미확정된 오른편의 항에 대입되고, 그 왼쪽의 그룹이 스택에 푸시됨으로써, 점점 상위로 해결되어 간다.

토큰을 받은 상태 번호를 상태 스택에 넣었다 빼면 완전 동기화되어, (있으면) 그 토큰의 의미값도 의미값 스택에 넣었다 뺀다. 이것에 의해 액션에 의한 의미값 계산을 보증하고 있다.

최종 목표는 전부 읽었을 때, "%start"로 지정되어 분석을 시작한 비종단 기호(디폴트는 처음에 쓰여 있는 규칙의 왼편)가 변환의 결과 $accept 1개로 환원될 수 있었는지를 조사하는 것이다.

만약 그것이 되지 않았다면, 입력 문자열은 이 문법에 적합하지 않은 에러라는 것을 알 수 있다.

만약 가능했다면, 이 문법에 적합하다고 판단할 수 있으며, 그것에 직접 또는 재귀적으로 내포되는 모든 요소에 해당하는 입력 토큰 열이 확정된다.

7. 2. 파서의 동작 과정

Yacc가 생성하는 구문 분석기는 내부 스택을 가진 유한 상태 기계이다. 구문 분석기는 다음의 과정을 반복 수행한다.[32]

  • 현재 상태에서 선행(lookahead) 토큰이 필요하고 현재 그것이 설정되어 있지 않으면, yylex()를 호출하여 선행 토큰을 받는다.
  • 그리고 현재 상태와 선행 토큰에 의해 결정되는 액션을 실행한다.


Yacc는 분석 테이블에 이 기계의 액션들을 전개하는데, 가능한 액션의 종류는 다음과 같다.[32]

액션 종류설명
시프트(shift)선행 토큰을 스택에 추가한다. 선행 토큰은 소비된다.
환원(reduce)n번째 규칙의 오른쪽에 있는 기호들을 왼쪽의 비종단 기호로 치환하여, 스택에서 오른쪽 기호들에 해당하는 요소를 제거한다. 그리고 왼쪽의 비종단 기호를 스택에 추가한다. 의미값이 있으면, 반환값에서 설정된다. 환원을 실행하는 조건은 분석 테이블에 "."(또는 "$default")라고 쓰여 있으면 무조건 실행, "MINUS" 등과 같이 선행 토큰 값이 주어질 때는 그것이 일치할 때에만 실행된다.
전이(goto)생성된 비종단 기호를 shift한다. 다음 종단 기호는 이 뒤의 shift에 맡겨진다. 선행 토큰은 소비되지 않는다.
수락(accept)구문 분석의 정상 종료이며, yyparse()에서 반환값 0으로 정상 복귀한다. yylex()에서 0 또는 음수가 반환되어 다음 종단 기호가 끝을 의미하는 $end가 되었을 때, 규칙 0 "$accept: 전체의 비종단 기호명 $end"에 의해 스택이 올바르게 $accept의 1개로 환원될 수 있을 때 실행된다.
에러(error)분석 테이블의 빈 칸, 즉 다음에 나타나서는 안 되는 종단 기호가 있을 때 매치되도록 전개된다. 구문 분석기는 에러를 검출하면, "error" 토큰이 정상적으로 일치하는 규칙을 찾을 때까지 스택을 팝업하면서 돌아간다. 찾으면 거기에 "error"라는 토큰이 있었다고 간주하여, 검출되는 규칙의 액션을 실행한다. 그리고 선행 토큰은 에러를 일으킨 토큰으로 진행한다(리셋). Yacc는 에러 다발 방지를 위해 토큰 3개의 읽기 및 시프트가 성공할 때까지 이 에러 상태에 머무르지만, 사용자가 액션에서 yyerrok(에러 회복) 매크로를 실행하면 그 도중에도 정상 상태로 돌아간다.



가능한 환원은 그대로 몇 번 실행한 후에 토큰은 시프트된다.

구문 분석기는 입력된 토큰들을 스택에 넣었다가 차례로 규칙 적용을 시도하고, 성공할 때마다 환원한다. 그리고 테이블의 지정에 따라 상태 전이해 간다.

최종 목표는 전부 읽었을 때, "%start"로 지정되어 분석을 시작한 비종단 기호 (디폴트는 처음에 써 있는 규칙의 왼편)가 변환의 결과 $accept 1개로 환원될 수 있었는지를 조사하는 것이다.

만약 그것이 되지 않았다면, 입력 문자열은 이 문법에 적합하지 않은 에러라는 것을 알 수 있다.

만약 그것이 가능했다면, 이 문법에 적합하다고 판단할 수 있으며, 그것에 직접 또는 재귀적으로 내포되는 전부의 요소에 해당하는 입력 토큰 열이 확정된다.

7. 3. 의미 값 처리

토큰의 의미 값은 의미 값 스택에 넣었다 빼는 방식으로 처리된다. 액션을 통해 의미 값을 계산하고 전달할 수 있다. 예를 들어, 다음 Yacc 코드에서[30]:

```c

qa: expr { printf(" Ans = %Lg", $1); prompt(); } /* 규칙 5 개행으로 계산, 표시. */

```

`qa`가 `expr`에 일치하면, `printf(" Ans = %Lg", $1); prompt();` 액션이 실행된다. 이때 `$1`은 `expr`의 의미 값을 나타낸다.

다음 코드에서,

```c

expr: NUM /* 규칙 6 「$$=$1;」는 생략 가능 */

| expr '+' expr { $$ = $1 + $3; } /* 규칙 9 덧셈. */

```

규칙 6은 숫자 토큰 `NUM`이 오면, 그 자체로 `expr`이 됨을 의미한다. 규칙 9는 `expr '+' expr` 배열 또한 `expr`임을 나타내며, 이때 액션 `{ $$ = $1 + $3; }`을 통해 덧셈 연산을 수행한다. 여기서 `$$`는 현재 규칙(여기서는 `expr`)의 의미 값을, `$1`은 첫 번째 `expr`의 의미 값을, `$3`은 세 번째 `expr`의 의미 값을 나타낸다. 즉, 두 `expr`의 의미 값을 더하여 현재 `expr`의 의미 값으로 설정한다.

토큰에 의미 값이 수반되는 경우, "%union"을 통해 취할 수 있는 형태를 열거하여 정의한다. 그리고 "%token"으로 ""처럼 공용체의 어떤 멤버인지를 명시할 수 있다. 액션에서 "$$"라고 쓰인 의미 값은 C 언어로 변환될 때 "lval.ldval"처럼 공용체의 요소를 가리키도록 자동 변환된다. 이러한 방식으로 의미 값이 전달된다.[30]

Yacc는 바텀업 구문 분석 방식으로 동작한다. 즉, 입력 토큰을 스택에 넣고, 규칙에 맞는 부분을 찾아 의미 값을 계산하며, 최종적으로 전체 문장이 시작 기호에 일치할 때까지 이 과정을 반복한다.[30]

8. 모호한 문법 처리

Yacc에서 모호한 문법을 사용하면 "환원/환원 충돌 경고" 또는 "시프트/환원 충돌 경고"가 발생한다. 이러한 경고는 문법을 개선하거나 구문 규칙을 수정할 수 있는 기회를 제공한다.

"환원/환원 충돌"은 파서가 올바르게 처리할 수 없는 구문 요소가 있을 때 발생하므로, 문법 또는 구문 규칙의 Yacc 정의를 수정해야 한다. 어떤 비종단 기호에서 다른 비종단 기호로 이어지는 호출 경로가 여러 개 있다면 수정해야 한다.

"시프트/환원 충돌"의 경우, Yacc는 기본적으로 시프트를 선택한다. 예를 들어, 다음 코드에서 `expr2`가 성립하지 않을 때 `stmt2`를 실행하도록 파서 테이블이 만들어진다.

```

IF expr1 IF expr2 stmt1; ELSE stmt2;

```

이는 가까운 기호의 관계를 우선하는 동작 방식으로, 많은 프로그래밍 언어 컴파일러에 적합하지만 주의가 필요하다.

Yacc 실행 시 충돌이 보고되거나 파서 실행 시 올바른 입력이 구문 오류(syntax error)로 처리될 때는 다음과 같이 대처할 수 있다.


  • 구문 오류 발생 시 토큰 값, 상태 스택 내 상태 번호 열, 소스 파일 상 행 번호 및 문자 번호를 출력하여 정확한 조사를 돕는다.
  • 비종단 기호에서 다른 비종단 기호로 이어지는 호출 경로가 여러 개 있다면 수정한다.
  • "토큰 또는 공백"과 같은 비종단 기호를 하나의 구문 우변에 여러 개 나열하면 충돌이 발생할 수 있으므로, 생략 없는 토큰만 사용하고 생략 가능 여부에 따라 모든 조합을 OR(|) 결합 형태로 변경한다.
  • 리스트의 리스트는 반복 요소에 `in` 등의 접두사적인 토큰이 따르지 않으면 모호성이 발생할 수 있으므로, 리스트 단계 수를 줄여 명확하게 한다.
  • 문제의 비종단 기호를 사용하는 장면마다 다른 토큰으로 구성하도록 정의를 변경하고, Lex 단계에서 장면에 따라 토큰을 변환하여 구분한다.
  • `y.output` 파일에서 해당 상태 번호를 찾아 숙독하고, 상태 번호로 전이되는 상태를 추적하여 얽힌 토큰을 조사한다.
  • 원인 조사가 어려울 경우, 문제가 되는 문법 요소 주변 정의만 추출한 "미니 문법"을 Yacc 정의하여 문제를 분리한다.
  • 혼란을 야기하는 토큰을 포함하는 연속된 2개 이상의 토큰을 Lex 단계에서 1개의 별도 토큰으로 묶어 명확하게 한다.
  • Lex 단계에서 내부 상태를 갖고, 들어오는 토큰을 보면서 상태 전이하여 문제 부분을 검출하고, 다른 토큰으로 변경하거나 특별한 토큰을 삽입하여 명확하게 한다.
  • Bison 실행에서 보고되는 충돌 수가 감소하면 효과가 있는 경우가 많지만, 감소하지 않더라도 특정 입력 처리가 개선될 수 있다.
  • 입력 언어가 너무 복잡하거나 프리프로세서 명령을 포함하는 경우, 파싱을 2단계 직렬 구성으로 하는 해결책도 있다.

8. 1. 충돌 경고

Yacc에서 모호한 문법을 사용하면 "환원/환원 충돌 경고" 또는 "시프트/환원 충돌 경고"가 발생한다. 이러한 경고는 문법을 개선하거나 구문 규칙을 수정할 수 있는 기회를 제공한다.

"환원/환원 충돌"은 파서가 올바르게 처리할 수 없는 구문 요소가 있을 때 발생하므로, 문법 또는 구문 규칙의 Yacc 정의를 수정해야 한다. 어떤 비종단 기호에서 다른 비종단 기호로 이어지는 호출 경로가 여러 개 있다면 수정해야 한다.

"시프트/환원 충돌"의 경우, Yacc는 기본적으로 시프트를 선택한다. 예를 들어, 다음 코드에서 `expr2`가 성립하지 않을 때 `stmt2`를 실행하도록 파서 테이블이 만들어진다.

```

IF expr1 IF expr2 stmt1; ELSE stmt2;

```

이는 가까운 기호의 관계를 우선하는 동작 방식으로, 많은 프로그래밍 언어 컴파일러에 적합하지만 주의가 필요하다.

Yacc 실행 시 충돌이 보고되거나 파서 실행 시 올바른 입력이 구문 오류(syntax error)로 처리될 때 다음과 같이 대처할 수 있다.

  • 구문 오류 발생 시 토큰 값, 상태 스택 내 상태 번호 열, 소스 파일 상 행 번호 및 문자 번호를 출력하여 정확한 조사를 돕는다.
  • 비종단 기호에서 다른 비종단 기호로 이어지는 호출 경로가 여러 개 있다면 수정한다.
  • "토큰 또는 공백"과 같은 비종단 기호를 하나의 구문 우변에 여러 개 나열하면 충돌이 발생할 수 있으므로, 생략 없는 토큰만 사용하고 생략 가능 여부에 따라 모든 조합을 OR(|) 결합 형태로 변경한다.
  • 리스트의 리스트는 반복 요소에 `in` 등의 접두사적인 토큰이 따르지 않으면 모호성이 발생할 수 있으므로, 리스트 단계 수를 줄여 명확하게 한다.
  • 문제의 비종단 기호를 사용하는 장면마다 다른 토큰으로 구성하도록 정의를 변경하고, Lex 단계에서 장면에 따라 토큰을 변환하여 구분한다.
  • `y.output` 파일에서 해당 상태 번호를 찾아 숙독하고, 상태 번호로 전이되는 상태를 추적하여 얽힌 토큰을 조사한다.
  • 원인 조사가 어려울 경우, 문제가 되는 문법 요소 주변 정의만 추출한 "미니 문법"을 Yacc 정의하여 문제를 분리한다.
  • 혼란을 야기하는 토큰을 포함하는 연속된 2개 이상의 토큰을 Lex 단계에서 1개의 별도 토큰으로 묶어 명확하게 한다.
  • Lex 단계에서 내부 상태를 갖고, 들어오는 토큰을 보면서 상태 전이하여 문제 부분을 검출하고, 다른 토큰으로 변경하거나 특별한 토큰을 삽입하여 명확하게 한다.
  • Bison 실행에서 보고되는 충돌 수가 감소하면 효과가 있는 경우가 많지만, 감소하지 않더라도 특정 입력 처리가 개선될 수 있다.
  • 입력 언어가 너무 복잡하거나 프리프로세서 명령을 포함하는 경우, 파싱을 2단계 직렬 구성으로 하는 해결책도 있다.

8. 2. 충돌 및 구문 에러 해결 방법

Yacc에서 문법의 모호성으로 인해 발생하는 충돌 경고("환원/환원 충돌", "시프트/환원 충돌") 및 구문 에러를 해결하기 위한 방법은 다음과 같다.

  • `yyerror()` 함수 개선: 구문 에러 발생 시, 최소한 토큰 값, 상태 스택 내 상태 번호, 소스 파일 상의 행/문자 번호를 출력하도록 `yyerror()` 함수를 수정하여 정확한 조사를 돕는다.
  • 비터미널 기호 경로 점검: 어떤 비터미널 기호에서 다른 비터미널 기호로 이어지는 호출 경로가 여러 개 있다면 수정한다.
  • 생략 가능 토큰 최소화: "토큰 또는 공백"과 같이 생략 가능한 토큰을 하나의 구문 우변 안에 여러 개 나열하면 충돌이 발생할 수 있다. 생략 없는 토큰만 사용하고, 생략 여부에 따른 모든 조합을 명시적으로 열거한다.
  • Lex 단계 처리:
  • 혼란을 야기하는 토큰을 포함하는 연속된 2개 이상의 토큰을 Lex 단계에서 1개의 별도 토큰으로 묶어 명료화한다.
  • 파서의 시프트나 환원 상태만으로 기술할 수 없는 장면은 Lex 단계에서 내부 상태를 이용하여 식별하고, 토큰을 변경하거나 삽입하여 명료화한다.
  • 2단계 파싱: 입력 언어가 너무 복잡하거나 프리프로세서 명령을 포함하는 경우, 파싱을 2단계로 나누어 처리한다. 첫 단계는 간단한 문법으로 모호성을 해결하고, 그 결과를 두 번째 단계의 파서에 전달한다.

참조

[1] 웹사이트 The A-Z of Programming Languages: YACC https://web.archive.[...] Computerworld 2012-11-30
[2] 서적 Lex & yacc https://archive.org/[...] O'Reilly & Associates
[3] 서적 Flex & bison O'Reilly Media
[4] 뉴스 Stephen Curtis Johnson: Geek of the Week https://www.red-gate[...] 2009-10-01
[5] 뉴스 Stephen Curtis Johnson: Geek of the Week https://www.red-gate[...] 2009-10-01
[6] 웹사이트 Early Translator Writing Systems http://www.chilton-c[...] Atlas Computer Laboratory
[7] 간행물 The Development of the C Language Association for Computing Machinery, Inc. 1993-04
[8] 간행물 A Research Unix reader: annotated excerpts from the Programmer's Manual, 1971–1986 http://www.cs.dartmo[...]
[9] 간행물 Yacc: Yet Another Compiler-Compiler http://dinosaur.comp[...] AT&T Bell Laboratories 2020-01-31
[10] 웹사이트 A History of C++: 1979−1991 http://www.stroustru[...]
[11] 웹사이트 Cfront source code http://www.softwarep[...]
[12] 뉴스 Yacc, Unix, and advice from Bell Labs alumni Stephen Johnson https://www.computer[...] 2008-07-09
[13] 문서 cu lex
[14] 웹사이트 plan9: UC Berkeley release of Plan 9 under the GPLv2 https://github.com/b[...] 2017-12-26
[15] 문서 Bison Manual: History https://www.gnu.org/[...]
[16] 서적 The Insider's Guide To The Universe https://www.1000bit.[...] Charles River Data Systems, Inc.
[17] 웹사이트 Cfront source code http://www.softwarep[...]
[18] Youtube UNIX Special: Profs Kernighan & Brailsford https://www.youtube.[...] 2015-09-30
[19] 서적 The Unix Programming Environment Prentice Hall
[20] 웹사이트 OCaml User's Manual: Chapter 12 Lexer and parser generators (ocamllex, ocamlyacc) http://caml.inria.fr[...] 2013-11-25
[21] 웹사이트 Yacc.go: A version of Yacc for the Go Programming Language https://godoc.org/go[...] 2017-07-15
[22] 웹사이트 CL-Yacc: A Common Lisp version of Yacc http://www.pps.univ-[...]
[23] 웹사이트 yecc: An Erlang implementation of Yacc http://erlang.org/do[...]
[24] 문서 flex & bison O'Reilly Media 2009-08
[25] 문서 semantic value
[26] 문서 lexical analyzer
[27] 문서 fast lexical analyzer generator
[28] 문서 Theory of Compilation -- JLex, CUP tools -- http://cs.haifa.ac.i[...]
[29] 문서 POSIX 1003.1-2008 http://standards.iee[...]
[30] 문서 An Overview of Parser Generator Tools for Java http://www.cs.iastat[...]
[31] 문서 G・フリードマン著、矢吹道郎ら訳、竹本 浩OCR復刻 Cコンパイラ設計(yacc・lexの応用) http://www.pwv.co.jp[...]
[32] 문서 パーサーの操作 http://docs.oracle.c[...]
[33] 문서 A yacc tutorial http://www.cs.arizon[...]
[34] 문서 Yacc: A Parser Generator ftp://netlib.bell-la[...]
[35] 문서 Understanding Bison 2.7 8.1 Understanding Your Parser http://www.gnu.org/s[...]


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com