연산자 프리텐스 문법

연산자 우선 문법은 형식 언어의 문법의 일종이다.

기술적으로, 연산자 우선 문법은 문맥이 없는 문법으로서, 생산물이 빈 오른쪽이나 두 개의 인접한 비단어가 그 오른쪽에 있는 속성(다른^[1] 것 중)을 가지고 있지 않다.이러한 속성은 문법의 단자 사이에 우선 관계를 규정할 수 있게 한다.이러한 관계를 이용하는 파서는 LALR 파서와 같은 더 많은 범용 파서보다 상당히 간단하다.연산자 프리덴스 파서는 많은 종류의 무 컨텍스트 그래머에 대해 구성할 수 있다.

우선 관계

운영자 우선 순위 그래머는 터미널 간의 다음 세 가지 우선 순위 관계에 의존한다.^[2]

관계	의미
$a\lessdot b}$	b보다 수확량이 우선하다.
$a\doteq b}$	a가 b와 같은 우선권을 가지다
$a\displaystyle a\gtrdot b}$	a가 b보다 우선하다

이러한 연산자 우선 순위 관계에서는 핸들을 오른쪽 sential 형식으로 구분할 수 있다. :${\displaystyle \lessdot }$은(는) 왼쪽 끝을 표시하고, $,{\displaystyle }$${\displaystyle \dot$ $}$은$($는) 오른쪽 끝을 표시한다.다른 시프트-리듀스 파서와는 달리 모든 비터미널은 핸들을 식별하기 위한 목적으로 동등하다고 간주된다.^[3]The relations do not have the same properties as their un-dotted counterparts; e. g. ${\displaystyle a\doteq b}$ does not generally imply ${\displaystyle b\doteq a}$, and ${\displaystyle b\gtrdot a}$ does not follow from ${\displaystyle a\lessdot b}$. Furthermore, ${\displaystyle a\doteq a$$}$은(는) 일반적으로 유지되지 않으며$$ ${\displaystyle \{}$ ${\displaystyle$ a$\gtrdot$ a$}$이(가) 가능하다.

단자 a와_i a 사이에는_i+1 항상 하나의 우선 관계가 있다고 가정해 보자.$가 줄의 끝이라고 가정하자.Then for all terminals b we define: ${\displaystyle \$\lessdot b}$ and ${\displaystyle b\gtrdot \$}$. If we remove all nonterminals and place the correct precedence relation: ${\displaystyle \lessdot }$, ${\displaystyle \doteq }$, ${\displaystyle \gtrdot }$ between the remaining terminals, there rem쉽게 발달한 바텀업 파서로 분석할 수 있는 문자열.

예

예를 들어 간단한 표현에 대해 다음과 같은 연산자 우선 관계를 도입할 수 있다.^[4]

${\displaystyle {\begin{array}{c cccc}&\mathrm {id} &+&*&\$\\\hline \mathrm {id} &&\gtrdot &\gtrdot &\gtrdot \\+&\lessdot &\gtrdot &\lessdot &\gtrdot \\*&\lessdot &\gtrdot &\gtrdot &\gtrdot \\\$$BODY$$amp;\lessdot &\lessdot &\lessdot &\end{array}}}$

그들은 다음과 같은 사실에서 따온 것이다.^[5]

• + 우선 순위가 *보다 낮음(이름 +${\displaystyle ⋖}$ ∗ ${\displaystyle \ast }$ ${\displaystyle +\lessdot *}$ 및$$ $\ast {\displaystyle }$ ${\displaystyle ⋗}$+ ${\displaystyle *\gtrdot +}).$
• +와 *는 모두 왼쪽 연관성(헨스${\displaystyle }$+ ${\displaystyle ⋗}$+ ${\displaystyle$ + {\displaystyle $+\gtrdot +}$ 및${\displaystyle }$and$$ ⋗ ⋗$$ {\$displaystyle *\gtrdot *})$이다.$$

입력 문자열^[4]

${\displaystyle \mathrm {id} _{1}+\mathrm {id} _{2}*\mathrm {id} _{3}}}}$

엔드 마커를 추가하고 우선 순위 관계를 삽입한 후

${\displaystyle \$\lessdot \mathrm {id} _{1}\gtrdot +\lessdot \mathrm {id} _{2}\gtrdot *\lessdot \mathrm {id} _{3}\gtrdot \$}$

연산자 우선 순위 구문 분석

우선 순위 관계를 가지면 다음과 같이 핸들을 식별할 수 있다.^[4]

• 문자열을 왼쪽에서 검색하여 $▼{\displaystyle }$ ${\displaystyle \gtrdot }$ 확인
• $▼{\displaystyle }$ ${\displaystyle \doteq }$을(를) 확인할 때까지$$ 뒤로(오른쪽에서 왼쪽으로) 스캔
• 간섭 또는 주변 비터미널을 포함하여 두 관계 $⋖{\displaystyle }$ ${\displaystyle \lessdot }$과(와) $⋗{\displaystyle }$ ${\displaystyle \gtrdot }$ 사이의 모든 것이 핸들을 형성한다$.$

일반적으로 핸들을 찾기 위해 전체 보초 양식을 스캔할 필요는 없다.

연산자 우선 순위 구문 분석 알고리즘^[6]

$가 스택의 맨 위에 있고 ip가 $를 가리킬 경우, ip가 스택의 최상위 터미널이 되게 하고, b 기호가${\displaystyle }$ip ${\displaystyle \lessdot }$ 또는 $\doteq {\displaystyle }$ ${\$$displaystyle$ $\doteq }$ stack advanced ip를 다음 입력 기호로 밀어 넣는다$.$$\gtrdot$$\}{\displaystyle }$$b$ 그런 다음 상단 스택 터미널이 recently ${\displaystyle \lessdot }$과(와) 가장 최근에 펑크 난 터미널에 연관될 때까지 스택을 반복한다. 그렇지 않으면 오류 발생 끝

우선 순위 함수

연산자 우선 순위 분석기는 대개 관계가 있는 우선 순위 표를 저장하지 않으며, 이는 상당히 커질 수 있다.대신 f와 g의 우선 함수가 정의된다.^[7]그들은 단자 기호를 정수에 매핑하고, 그래서 기호들 사이의 우선관계는 숫자 비교에 된다: f ) <( b) {\$displaystyle$ f$(a)}<g(b)}$은 ${\displaystyle ⋖}$ ${\displaystyle b}$ ${\displaysty a\lessdot b}$이(가)를$$ 보유할 경우 고정되어야 한다.

우선순위 관계의 모든 표에 우선순위 함수가 있는 것은 아니지만, 실제로 대부분의 문법에서는 그러한 함수를 설계할 수 있다.^[8]

우선 순위 함수를^[9] 구성하는 알고리즘

1. 각 문법 단자 a와 문자열 끝에 대한 기호 f와_a g를_a 작성한다.
2. ${\displaystyle \mathrm{symbols}}$ b ${\displaystyle a\doteq b}$인 경우 f와_a g가_b 같은 그룹에 있도록 생성된 기호를 그룹으로 분할한다($$이 관계에 의해 단자가 연결되지 않은 경우에도 동일한 그룹에 기호가 있을 수 있음).
3. 노드가 그룹인 방향 그래프를 만드십시오.각_b 단자 쌍$({\displaystyle }$ ,${\displaystyle b}$) ${\displaystyle (a,b)}$에 대해: ${\displaystyle ⋖}$ ${\displaystyle b}$ ${\displaystyle a\lessdot$ b$\},$ 그렇지 $않으면{\displaystyle }${ b ${\displaystyle a\gtot b}$이(가) f_a 그룹에서_ab g 그룹까지 에지를 배치할$$ 경우;
4. 생성된 그래프에 주기가 있으면 우선 순위 함수가 존재하지 않는다.주기가 없는 경우 ${\displaystyle f}$(${\displaystyle }$) ${\displaystyle f(a)}$을(를) f_a 그룹에서 가장 긴 경로의 길이로 하고$$ $g{\displaystyle }$ (${\displaystyle }$) ${\displaystyle g(a)}$을(를) g_a 그룹에서 가장 긴 경로의 길이로 한다$$.

예

다음 표를 고려하십시오(^[10]위에서 반복).

${\displaystyle {\begin{array}{c cccc}&\mathrm {id} &+&*&\$\\\hline \mathrm {id} &&\gtrdot &\gtrdot &\gtrdot \\+&\lessdot &\gtrdot &\lessdot &\gtrdot \\*&\lessdot &\gtrdot &\gtrdot &\gtrdot \\\$$BODY$$amp;\lessdot &\lessdot &\lessdot &\end{array}}}$

알고리즘을 사용하면 다음 그래프를 볼 수 있다.

gid \ fid f* \ / g* / f+ \ g+ g$ f$

여기서 지시된 반복 그래프의 최대 높이에서 다음과 같은 우선 순위 함수를 추출한다.

	id	+	*	$
f	4	2	4	0
g	5	1	3	0

연산자 사전 언어

운영자-절차 언어, 즉 운영자-절차 언어에 의해 기술되는 언어의 클래스는 결정론적 맥락 없는 언어의 클래스에 엄격히 포함되며, 눈에 띄게 푸시다운 언어를 엄격하게 포함한다.^[11]

연산자 사전 언어들은 결합, 교차로, 보완,^[12] 결합과 같은 많은 폐쇄 속성을 즐기고 있으며,^[11] 그것들은 이러한 모든 운영 하에서 폐쇄되고 비어있는 문제가 해결될 수 있는 것으로 알려진 가장 큰 등급이다.연산자 프리덴스 언어의 또 다른 독특한 특징은 효율적인 병렬 파싱이 가능한 로컬 파싱이다.^[13]

또한 등가 형태의 오토마타와 단음이의 2차 논리학에 기초한 특성화도 있다.^[14]

메모들

참조

• 아호, 알프레드 5세, 세티, 라비, 울만, 제프리 D. (1988년)컴파일러 — 원칙, 기술 및 도구.애디슨 웨슬리
• Floyd, R. W. (July 1963). "Syntactic Analysis and Operator Precedence". Journal of the ACM. 10 (3): 316–333. doi:10.1145/321172.321179. S2CID 19785090.
• Crespi Reghizzi, Stefano; Mandrioli, Dino (2012). "Operator precedence and the visibly pushdown property". Journal of Computer and System Sciences. 78 (6): 1837–1867. doi:10.1016/j.jcss.2011.12.006.
• Crespi Reghizzi, Stefano; Mandrioli, Dino; Martin, David F. (1978). "Algebraic Properties of Operator Precedence Languages". Information and Control. 37 (2): 115–133. doi:10.1016/S0019-9958(78)90474-6.
• Barenghi, Alessandro; Crespi Reghizzi, Stefano; Mandrioli, Dino; Panella, Federica; Pradella, Matteo (2015). "Parallel parsing made practical". Science of Computer Programming. 112 (3): 245–249. doi:10.1016/j.scico.2015.09.002.
• Lonati, Violetta; Mandrioli, Dino; Panella, Federica; Pradella, Matteo (2015). "Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization". SIAM Journal on Computing. 44 (4): 1026–1088. doi:10.1137/140978818. hdl:2434/352809.

외부 링크

• 니콜라이 니콜라예프: IS53011A 언어 설계 및 구현, 코스 노트(CIS 324, 2010)