연산자 준비 분석기

Operator-precedence parser

컴퓨터 과학에서 연산자 우선 분석기는 연산자 사전 문법을 해석하는 상향식 분석기다.예를 들어 대부분의 계산기는 연산 순서에 의존하는 사람이 판독할 수 있는 인픽스 표기법에서 역폴란드어 표기법(RPN)과 같이 평가에 최적화된 형식으로 변환하기 위해 연산자 우선 구문 분석기를 사용한다.

Edsger Dijkstra의 션팅 야드 알고리즘은 일반적으로 연산자 우선 파서 구현에 사용된다.

다른 파서와의 관계

연산자 프리덴스 파서는 LR(1) 그래머의 서브셋을 구문 분석할 수 있는 간단한 시프트 리듀스 파서다.더 정확히 말하면, 연산자 사전 분석기는 모든 LR(1) 그래머를 구문 분석할 수 있다. 여기서 연속 2개의 비터미널과 엡실론은 어떤 규칙의 우측에 나타나지 않는다.

연산자 프리덴스 파서는 실무에서 자주 사용되지 않지만, 더 큰 설계 내에서 유용하게 사용할 수 있는 몇 가지 특성을 가지고 있다.첫째, 손으로 쓸 수 있을 정도로 간단하다. 이것은 일반적으로 더 정교한 오른쪽 시프트-리듀스 파서들의 경우는 아니다.둘째, 런타임에 연산자 테이블을 참조하기 위해 작성할 수 있어 파싱하는 동안 연산자를 추가하거나 변경할 수 있는 언어에 적합하다(예: 사용자 정의 infix 연산자가 사용자 정의 연관성과 우선 순위를 가질 수 있도록 하는 Haskell). 따라서 연산자-정합성 분석기를 프로그램에서 실행해야 한다.참조된 모든 모듈의 구문 분석 후)

라쿠는 속도와 역동성의 균형을 이루기 위해 두 재귀 강하 파서 사이에서 교환수 프리덴스 파서(operator-precedence parser)를 샌드위치처럼 만들었다.GCC의 C와 C+++ 파서 모두 손으로 코딩한 재귀 강하 파서들이 산술적 표현을 빠르게 검사할 수 있는 연산자 프리덴스 파서(operator-preference parser)에 의해 속도를 낸다.연산자 우선 구문 분석기는 표현 파싱에 대한 재귀 강하 접근의 속도를 눈에 띄게 높이기 위해 컴파일러-컴파일러 생성 구문 분석기에도 내장되어 있다.[1]

우선등반방법

우선등반방식은 마틴 리차드와 콜린 휘트비-스트레벤스가 처음 설명한 표현을 파싱하기 위한 콤팩트하고 효율적이며 유연한 알고리즘이다.[2]

EBNF 형식의 infix-notation 표현 문법은 보통 다음과 같이 보일 것이다.

expression ::= equality-expression equality-expression ::= additive-expression ( ( '=='   '!=' ) additive-expression ) * additive-expression ::= multiplicative-expression ( ( '+'   '-' ) multiplicative-expression ) * multiplicative-expression ::= primary ( ( '*'   '/' ) primary ) * primary ::= '(' expression ')'   NUMBER VARIABLE   '-' primary

많은 수준의 우선 순위에 따라, 예측 재귀성 파서로 이 문법을 구현하는 것은 비효율적일 수 있다.예를 들어, 숫자를 구문 분석하려면 5개의 함수 호출이 필요할 수 있다: 1차적 기능에 도달할 때까지 문법에서 각 비단어마다 하나씩.

운영자 사전 분석기는 보다 효율적으로 동일한 작업을 수행할 수 있다.[1]같은 우선 순위를 가진 연산자를 찾는 한 산술 연산을 연관시킬 수 있지만, 더 높은 우선 순위 연산자를 평가하기 위해서는 임시 결과를 저장해야 한다는 생각이다.여기에 제시된 알고리즘은 명시적 스택이 필요하지 않다. 대신, 스택을 구현하기 위해 재귀적 호출을 사용한다.

알고리즘은 Dijkstra shunting 야드 알고리즘과 같은 순수한 연산자 사전 파서가 아니다.그것은 1차 비터미널이 재귀 강하 파서와 같이 별도의 서브루틴으로 구문 분석된다고 가정한다.

가성음

알고리즘의 유사코드는 다음과 같다.파서는 함수 parse_expression에서 시작한다.우선 순위 수준이 0보다 크거나 같다.

parse_parset return parse_pars_1(parse_pars_parset 0)
lookahead가 다음 토큰을 parse_properties_1(seces, min_min_lights) lookahead:=next 토큰을 peek하는 동안 lookahead는 2진수 연산자보다 우선 순위가 큰 2진수 연산자:= min_light op := lookahead:=next 토큰을 peekops보다, 또는 op의 rhs := parse_op_1 (rhs, op의 우선순위 + (lookahead 우선순위가 더 큰 경우, 다른 0인 경우) lhs) lookahead :=다음 토큰 lhs :=feek next token lhs :=foss와 rhs return lhs로 op을 적용한 결과

이와 같은 프로덕션 규칙의 경우(사용자가 한 번만 나타날 수 있는 경우): 

equality-properties ::= addition ('='!=') additions

알고리즘은 우선 순위가 > min_messages인 이진 연산자만 허용하도록 수정되어야 한다.

알고리즘 실행 예

2 + 3 * 4 + 5 == 19 식에 대한 실행 예는 다음과 같다.우리는 평등 표현에 우선 순위 0을 부여하고, 가법 표현에 우선 순위를 부여하며, 승법 표현에 우선 순위를 부여한다.

parse_parces_1 (cs = 2, min_properties = 0)

  • 룩어헤드 토큰은 +이며, 우선 순위 1. 루프가 입력되는 동안 바깥쪽이 입력된다.
  • op은 +(수치 1)이고 입력은 고급이다.
  • rhs는 3이다.
  • 룩어헤드 토큰은 *이며 우선 순위 2. 내부 while 루프 입력.
    parse_pars_1 (cs = 3, min_properties = 2)
  • 룩어헤드 토큰은 *이며, 우선 순위 2. 루프가 입력되는 동안 바깥쪽이 입력된다.
  • op은 * (계속 2)이고 입력은 고급이다.
  • rhs는 4이다.
  • 다음 토큰은 +이며, 우선 순위 1. 내부 while 루프가 입력되지 않음.
  • lhs에 3*4 = 12가 할당됨
  • 다음 토큰은 +이며, 우선 순위 1. 루프가 남아 있는 동안 바깥쪽이 왼쪽이다.
  • 12가 돌아온다.
  • 룩어헤드 토큰은 +이며, 우선 순위 1. 내부 while loop이 입력되지 않음.
  • lhs에 2+12 = 14가 할당됨
  • 룩어헤드 토큰은 +이며, 우선 순위 1. 루프가 남아 있지 않은 동안 바깥쪽은 +이다.
  • op은 +(수치 1)이고 입력은 고급이다.
  • rhs는 5이다.
  • 다음 토큰은 ==, 우선 순위 0. 내부 while 루프가 입력되지 않음.
  • lhs에 14+5 = 19가 할당됨
  • 다음 토큰은 ==, 우선 순위 0. 루프가 남아 있지 않은 동안 바깥쪽이 남아 있다.
  • op은 ==(수치 0)이고 입력은 고급이다.
  • rhs는 19이다.
  • 다음 토큰은 운영자가 아닌 종단선(end-of-line)이다.루프가 입력되지 않은 동안 내부
  • lhs에는 19 == 19를 평가한 결과가 할당된다(예: 1(C 표준)).
  • 다음 토큰은 운영자가 아닌 종단선(end-of-line)이다.루프가 남아 있는 동안 바깥쪽

1은 반환된다.

프랫 파싱

Pratt 파싱으로 알려진 또 다른 우선 순위 분석가는 1973년 논문 "Top down 연산자 우선 순위"[3]에서 재귀적 강하에 기초하여 Vaughan Pratt에 의해 처음 설명되었다.선순위 상승을 앞섰지만 선순위 상승을 일반화한 것으로 볼 수 있다.[4]

Pratt는 원래 CGOL 프로그래밍 언어를 구현하기 위해 파서를 설계했고, 그것은 그의 감독 하에 석사 논문에서 훨씬 더 심도 있게 다루어졌다.[5]

자습서 및 구현:

대체 방법

운영자 우선 순위 규칙을 적용하는 다른 방법이 있다.하나는 원래 표현식의 트리를 만든 다음 트리 재작성 규칙을 적용하는 것이다.

그러한 트리는 일반적으로 나무에 사용되는 데이터 구조를 사용하여 반드시 구현될 필요는 없다.대신 토큰을 테이블과 같은 평평한 구조로 저장할 수 있는데, 그 순서에 따라 어떤 요소를 처리할 것인지에 대한 우선순위 목록을 동시에 작성할 수 있다.

또 다른 접근법은 먼저 표현식을 완전히 괄호 안에 삽입하여 각 연산자 주위에 여러 개의 괄호를 삽입하여 선형 좌우 구문 분석기로 구문 분석할 때에도 정확한 우선 순위를 유도하는 것이다.이 알고리즘은 초기의 FORTRAN I 컴파일러에서 사용되었다.[7]

Fortran I 컴파일러는 각 연산자를 일련의 괄호로 확장시킬 것이다.알고리즘의 단순화된 형태에서는

  • 대체하다+그리고–와 함께))+((그리고))-((각각,
  • 대체하다*그리고/와 함께)*(그리고)/(각각,
  • 덧셈을((각 표현식의 시작 부분과 원래 표현식의 각 왼쪽 괄호 뒤에 및
  • 덧셈을))원래 표현식의 각 오른쪽 괄호 앞에.

명백하지는 않지만 알고리즘은 정확했고, 크누스의 말에 의하면, "결과적인 공식은 적절히 괄호화되어 있다, 믿거나 말거나."[8]

기본 산술 연산자의 괄호화를 처리하는 단순 C 응용 프로그램의 예 코드 (+,-,*,/,^,(그리고)):

#include <stdio.h> #include < 현악기>h>  인트로 본래의(인트로 argc, 마를 뜨다 *아그브[]) {   인트로 i;   활자화하다("((((");   을 위해 (i=1;i!=argc;i++) {     만일 (아그브[i] && !아그브[i][1]) {       바꾸다 (*아그브[i]) {           케이스 '(': 활자화하다("(((("); 계속하다;           케이스 ')': 활자화하다("))))"); 계속하다;           케이스 '^': 활자화하다(")^("); 계속하다;           케이스 '*': 활자화하다("))*(("); 계속하다;           케이스 '/': 활자화하다("))/(("); 계속하다;           케이스 '+':             만일 (i == 1    발을 동동 구르다("(^*/+-", *아그브[i-1]))               활자화하다("+");             다른               활자화하다(")))+(((");             계속하다;           케이스 '-':             만일 (i == 1    발을 동동 구르다("(^*/+-", *아그브[i-1]))               활자화하다("-");             다른               활자화하다(")))-(((");             계속하다;       }     }     활자화하다("%s", 아그브[i]);   }   활자화하다("))))\n");   돌아오다 0; }

예를 들어 명령줄에서 매개 변수를 사용하여 컴파일하고 호출하는 경우

a * b + c ^ d / e

생산하다

(((a)**(b)+((c)^(d)/(e))))

콘솔의 출력대로

이 전략의 한계는 단일 사업자가 모두 infix 사업자보다 높은 우선순위를 가져야 한다는 것이다.상기 코드의 "음수" 연산자는 지수보다 우선 순위가 높다.이 입력으로 프로그램 실행

- a ^ 2

이 산출물을 생산하다.

(((-a)^(2)))

아마 의도된 것이 아닐 것이다.

참조

  1. ^ a b Harwell, Sam (2008-08-29). "Operator precedence parser". ANTLR3 Wiki. Retrieved 2017-10-25.
  2. ^ Richards, Martin; Whitby-Strevens, Colin (1979). BCPL — the language and its compiler. Cambridge University Press. ISBN 9780521219655.
  3. ^ 프랫, 본"탑다운 오퍼레이터 우선 순위"제1회 ACM SIGACT-SIG플랜 연례 프로그래밍 언어 원리 심포지엄의 진행 (1973년)
  4. ^ Norvell, Theodore. "Parsing Expressions by Recursive Descent". www.engr.mun.ca. The purpose of this post is to [... start] with precedence climbing and refactoring it to use the command pattern until we arrive at a Pratt parser. [This is the author who coined the term "precedence climbing".]
  5. ^ 반 데 밴터, 마이클 L. "CGOL 언어 시스템의 공식화 및 정확성 증명서"(마스터즈 논문)컴퓨터 과학 기술 보고서 MIT-LCS-TR-147(매사추세츠 주 캠브리지)을 위한 MIT 연구소.1975.
  6. ^ Crockford, D (2007-02-21). "Top Down Operator Precedence".
  7. ^ Padua, David (2000). "The Fortran I Compiler" (PDF). Computing in Science & Engineering. 2 (1): 70–75. Bibcode:2000CSE.....2a..70P. doi:10.1109/5992.814661.
  8. ^ Knuth, Donald E. (1962). "A HISTORY OF WRITING COMPILERS". Computers and Automation. Edmund C. Berkeley. 11 (12): 8–14.

외부 링크