구문 분석 규칙 - 서로 잘 어울리도록 만드는 방법

Question

그래서 저는 속도보다 유연성을 선호하는 파서를 하고 있습니다. 예를 들어 문법을 쉽게 작성할 수 있기를 바랍니다.까다로운 해결 규칙(yacc/bison 등에서 해야 하는 것처럼 충돌을 해결하기 위한 가짜 규칙 등)이 없습니다.

고정된 토큰 세트가 있는 손으로 코딩한 Lexer가 있습니다(예:PLUS, DECIMAL, STRING_LIT, NAME 등) 현재 세 가지 유형의 규칙이 있습니다.

• 토큰규칙:특정 토큰과 일치
• 순서 규칙:순서가 지정된 규칙 목록과 일치합니다.
• 그룹 규칙:목록의 모든 규칙과 일치합니다.

예를 들어 토큰 NAME(대략 /[A-Za-z][A-Za-z0-9_]*/)과 일치하는 TokenRule 'varAccess'와 [ 식, TokenRule(PLUS), 식].

Expression은 '할당' 또는 'varAccess'와 일치하는 GroupRule입니다(제가 테스트하고 있는 실제 규칙 세트는 좀 더 완전하지만 예제에서는 그렇게 할 것입니다).

하지만 이제 파싱하고 싶다고 가정 해 보겠습니다.

var1 = var2

그리고 파서가 규칙 표현식으로 시작한다고 가정해 보겠습니다(정의된 순서는 중요하지 않습니다. 우선순위는 나중에 해결됩니다).그리고 GroupRule 표현식이 먼저 '할당'을 시도한다고 가정해 보겠습니다.그런 다음 '표현식'이 '할당'에서 일치하는 첫 번째 규칙이므로 표현식을 다시 구문 분석하려고 시도하며 스택이 채워지고 컴퓨터가 예상대로 반짝이는 세그폴트에서 포기할 때까지 계속됩니다.

그래서 제가 한 일은 SequenceRules가 자신을 첫 번째 규칙에 '리프'로 추가하고 루트가 아닌 규칙이 되는 것입니다.루트 규칙은 파서가 먼저 시도하는 규칙입니다.그 중 하나가 적용되어 일치하면 하나가 일치할 때까지 각 리프를 하나씩 하위 적용하려고 시도합니다.그런 다음 더 이상 일치하는 항목이 없을 때까지 일치하는 리프의 리프를 시도합니다.

다음과 같은 표현식을 구문 분석할 수 있도록

var1 = var2 = var3 = var4

딱 맞습니다 =) 이제 흥미로운 내용입니다.이 코드는:

var1 = (var2 + var3)

구문 분석하지 않습니다.일어나는 일은 var1이 구문 분석되고(varAccess), 할당이 하위 적용되고, 표현식을 찾고, '괄호'를 시도하고, 시작하고, '(' 뒤의 표현식을 찾고, var2를 찾은 다음 '+ '')'를 기대했기 때문입니다.

왜 'var2 + var3'과 일치하지 않습니까?(그렇습니다. 요청하기 전에 '추가' SequenceRule이 있습니다).'추가'는 루트 규칙이 아니기 때문에(식별 표현 시작으로 표현식 등을 사용하여 무한 재귀를 피하기 위해) 리프는 SequenceRules에서 테스트되지 않습니다. 그렇지 않으면 다음과 같이 구문 분석됩니다.

reader readLine() println()

~처럼

reader (readLine() println())

(예:'1 = 3'은 varAccess의 리프인 add에서 예상되는 표현식입니다.

반면 우리는 그것이 왼쪽 연관이기를 원합니다.다음으로 구문 분석

(reader readLine()) println()

어쨌든 이제 SequenceRules 내에서 '1 + 2'와 같은 표현식을 구문 분석할 수 있어야 하는 문제가 발생했습니다.무엇을 해야 할까요?SequenceRules가 TokenRule로 시작되면 여기에 포함된 GroupRules가 리프에 대해 테스트되는 특별한 경우를 추가하시겠습니까?그 특별한 예 밖에서도 그것이 의미가 있습니까?아니면 리프에 대해 테스트해야 하는지 여부를 SequenceRule의 각 요소에 지정할 수 있어야 합니까?당신의 생각을 말해주십시오. (전체 시스템을 버리는 것 외에는 어쨌든 몇 달 안에 일어날 것입니다.)

추신:제발, 제발, "가서 이 400페이지짜리 책을 읽어보세요. 그렇지 않으면 시간을 낼 자격도 없습니다"와 같은 대답은 하지 마세요. 그럴 필요가 있다고 느끼면 자제하고 Reddit에 가서 비난하세요.좋아요?미리 감사드립니다.

Answer 1

LL(k) 파서(하향식 재귀, 자동 또는 손으로 작성 여부)는 왼쪽 재귀를 피하기 위해 문법 리팩토링이 필요하며 종종 특수한 예측 사양이 필요합니다(예:ANTLR)을 사용하여 k-token 예측을 처리할 수 있습니다.문법은 복잡하기 때문에 실험을 통해 k를 발견하게 되는데, 이는 정확히 피하고 싶은 것입니다.

YACC/LALR(1) 문법은 왼쪽 재귀 문제를 방지하며 이는 큰 진전입니다.나쁜 소식은 LALR(1)인 실제 프로그래밍 언어(Wirth의 원래 PASCAL 제외)가 없다는 것입니다.따라서 문법을 해킹하여 LR(k)에서 LALR(1)로 변경하고, 다시 이상한 경우를 노출하는 실험을 겪게 하고, 구문 분석기가 실행될 때 K-lookaheads를 처리하려고 문법 감소 논리를 해킹합니다. 발전기(YACC, BISON, ...이름을 지정하면) 1-lookahead 파서를 생성합니다.

GLR 파서(http://en.wikipedia.org/wiki/GLR_parser) 이 넌센스를 거의 모두 피할 수 있습니다.컨텍스트 프리 파서를 작성할 수 있다면 대부분의 실제 상황에서 GLR 파서는 추가 노력 없이 이를 파싱합니다.임의의 문법을 작성하려고 할 때 이는 엄청난 안도감을 줍니다.그리고 정말 좋은 GLR 파서는 트리를 직접 생성합니다.

BISON은 일종의 GLR 구문 분석을 수행하도록 향상되었습니다.원하는 AST를 생성하려면 여전히 복잡한 논리를 작성해야 하며, 실패한 파서를 처리하고 해당(실패한) 트리를 정리/삭제하는 방법에 대해 걱정해야 합니다.그만큼 DMS 소프트웨어 리엔지니어링 투킷 모든 컨텍스트 자유 문법에 대한 표준 GLR 파서를 제공하고 사용자 측의 추가 노력 없이 자동으로 AST를 구축합니다.모호한 트리는 자동으로 구성되며 구문 분석 후 의미 분석을 통해 정리될 수 있습니다.우리는 이를 사용하여 C를 포함한 30개 이상의 언어 문법을 정의했습니다. 여기에는 C++(파싱하기 어렵다고 널리 알려져 있지만 [YACC로 파싱하는 것은 거의 불가능하지만] 실제 GLR에서는 간단합니다);보다 C+++ 프런트 엔드 파서 및 AST 빌더 DMS 기반.

요점:간단한 방법으로 문법 규칙을 작성하고 이를 처리하는 파서를 얻으려면 GLR 파싱 기술을 사용하세요.바이슨 거의 공장.DM 정말 공장.

Answer 2

내가 가장 좋아하는 구문 분석 기술은 PEG 문법 사양에서 재귀 살해 (RD) 파서를 만드는 것입니다. 그들은 일반적으로 매우 빠르고 단순하며 유연합니다. 한 가지 좋은 장점은 별도의 토큰 화 패스에 대해 걱정할 필요가 없으며 문법을 일부 lalr 형태로 짜는 것에 대해 걱정하는 것은 존재하지 않습니다. 일부 PEG 라이브러리에는 [여기] [1]가 나열되어 있습니다.

죄송합니다. 이것이 시스템을 버릴 수 있다는 것을 알고 있지만 문제가 발생하여 게이트에서 거의 나가지 않고 PEG RD 파서로 전환하면 지금 두통을 제거 할 것입니다.