정의되지 않은 개수의 인수를 사용하여 표현식 구문 분석

Question

자체 제작 언어의 문자열을 일종의 트리로 구문 분석하려고 합니다. 예:

# a * b1 b2 -> c * d1 d2 -> e # f1 f2 * g

결과는 다음과 같습니다.

# a
  * b1 b2
    -> c
  * d1 d2
    -> e
# f1 f2
  * g

#, * 및 ->는 기호입니다.a, b1 등텍스트입니다.

그 이후로 나는 표현식을 평가하는 rpn 방법만 알고 있으며 현재 솔루션은 다음과 같습니다.각 기호 뒤에 단일 텍스트 토큰만 허용하면 표현식을 먼저 RPN 표기법으로 쉽게 변환할 수 있습니다(b = b1 b2;d = d1 d2;f = f1 f2) 여기에서 구문 분석합니다.

a b c -> * d e -> * # f g * #

그러나 텍스트 토큰과 기타 항목을 병합하는 것은 문제가 있는 것 같습니다.내 아이디어는 마커 토큰(M)을 만드는 것이었으므로 RPN은 다음과 같습니다.

a M b2 b1 M c -> * M d2 d1 M e -> * # f2 f1 M g * #

이는 또한 구문 분석 가능하며 문제를 해결하는 것 같습니다.

그것은 말했다:

1. 누구든지 그런 경험이 있고 그것이 그렇다고 말할 수 있거나 미래를 위한 실행 가능한 솔루션이 아니라고 말할 수 있습니까?
2. 정의되지 않은 연산자 개수로 표현식을 구문 분석하는 더 좋은 방법이 있습니까?
3. 좋은 자료를 알려 주실 수 있나요?

메모.예, 저는 이 예가 Lisp 접두어 표기법과 매우 유사하다는 것을 알고 있으며 아마도 대괄호를 추가하는 것이 좋을 수도 있지만 여기에는 경험이 없습니다.그러나 소스 텍스트에는 인공 괄호가 포함되어서는 안 되며 # a * b -> [if value1 = value2] c -> d와 같은 잠재적인 삽입 믹스인에 대해 어떻게 해야 할지 잘 모르겠습니다.

도움을 주셔서 감사합니다.

편집하다:내가 찾고 있는 것은 가변 개수의 인수가 있는 후위 표기법의 소스인 것 같습니다.

Answer 1

귀하의 질문을 완전히 이해할 수는 없지만 귀하가 원하는 것은 문법 정의와 파서 생성기인 것 같습니다.꼭 살펴보시길 권합니다 ANTLR, 원래 구문이나 RPN에 대한 문법을 ​​정의하는 것은 매우 간단해야 합니다.

편집하다: (자기비판을 하고 문제 내용을 이해하려고 노력한 후) 실제로, 귀하의 예에서는 언어 문법이 명확하지 않습니다.그러나 제가 보기에는 접두사/접미사 표기법의 장점은 다음과 같습니다(예:괄호나 우선순위 인식 파서가 필요하지 않다는 점)은 인수의 수를 알아라 따라서 연산자를 만날 때마다 읽거나(접두사 표기의 경우) 스택에서 팝할(후위 표기의 경우) 요소 수를 정확히 알 수 있습니다.OTOH, 저는 가변 개수의 인수를 가질 수 있는 연산자를 사용하면 접두사/후위 표기법을 구문 분석하기 어려울 뿐 아니라 완전히 모호하게 만든다고 믿습니다.예를 들어 다음 표현식을 살펴보세요.

# a * b c d

다음 세 가지 중 표준 형식은 무엇입니까?

1. (a, *(b, c, d))

2. (a, *(b, c), d)

3. (a, *(b), c, d)

운영자에 대해 더 많이 알지 못하면 알 수 없습니다.물론 연산자의 탐욕을 정의할 수도 있습니다.*는 #보다 탐욕스럽기 때문에 모든 인수를 삼켜버립니다.그러나 이는 위의 세 가지 변형 중 두 번째 변형을 간단히 작성할 수 없기 때문에 접두사 표기법의 목적을 능가합니다.추가적인 구문 요소가 없으면 안 됩니다.

지금 생각해보면 내가 아는 프로그래밍 언어 중 어느 것도 지원하지 않는 것은 아마도 우연이 아닐 것입니다. 운영자 가변 개수의 인수를 사용하는 경우에만 기능/절차.