들소에서의 의미 론적 유형 검사 분석

Question

나는 어디에서나 예제를 찾으려고 노력했지만 헛된 것이었다.

기본 Ruby 인터프리터를 작성하려고합니다. 이를 위해 저는 토큰 인식 문장과 문법 파일을 포함하는 플렉스 어휘 파일을 작성했습니다.

내 문법에 의미 유형 검사가 포함되기를 바랍니다.

내 문법 파일은 예를 들어, 포함

arg : arg '+' arg 

이 정수와 수레에 유효한 규칙해야한다.

내가 읽은 바에 따르면, 그래서 같이 같은 인수와 같은 비 터미널 유형을 지정할 수 있습니다 : "INTVAL는"유형 조합에 있고 INT의 C 유형에 해당

%type <intval> arg 

.

그러나 이것은 정수에만 적용됩니다. 예를 들어, float에 유효한 규칙을 만드는 방법을 모르겠습니다. 내가 좋아하는, 두 개의 서로 다른 규칙의 int 하나와 수레 하나를하는 것에 대한 생각 :

argint : argint '+' argint 
argfloat : argfloat '+' argfloat 

하지만이 극악 가지고 저를 필요로하기 때문에 나는 그렇게 훨씬, 훨씬 더 나은 방법이 확신 float와 int 사이에 추가를 허용하는 규칙.

내가 발견 한 모든 예제에는 단 하나의 유형 만 있습니다 (보통 계산기와 같은 예제에서는 정수).

덧셈과 같은 규칙에 ints와 float을 인자로 사용할 수 있도록 지정하려면 어떻게해야합니까?

대단히 감사합니다.

Answer 1

이것은 당신이 바라는 답변이 아닙니다. 나는 당신이 원하는 것에 대한 예제를 보지 못했기 때문에 문법 파일 (.y)에 타이핑 규칙을 적용하는 것이 비현실적이라고 생각한다. 오히려 개발자는 절차 적 .c 또는 .cpp 코드로이를 수행합니다. 일반적으로 파싱 된 입력에 대한 분석은 어쨌든 수행 할 것이므로, 그렇게 할 때 의미 규칙을 적용하는 것은 부산물입니다.

제쳐두고, 나는 당신이 당신의 질문에서 재현 한 문법의 조각이 주어지면 어떻게 표현을 파싱하는지 이해하지 못합니다.

나는 이것이 비현실적이라고 주장하는 이유입니다. (1) 귀하의 유형 정보는 문법의 비단 말을 통해 모든 것을 여과해야합니다. (2) 나쁘면 변수 이름에 반영되어야한다.

식별자, 숫자 상수 및 4 개의 데스크 계산기 연산자를 사용할 수있는 간단한 할당 문을 구문 분석하는이 장난감 예를 생각해보십시오. NUMBER 토큰은 42와 같은 정수 또는 3.14와 같은 부동 소수점 수 있습니다. 그리고 신원이 A-Z라는 한 글자라고 가정 해 봅시다.

%token IDENTIFIER NUMBER 

%% 

stmt : IDENTIFIER '=' expr 
    ; 

expr : expr '+' term 
    | expr '-' term 
    | term 
    ; 

term : term '*' factor 
    | term '/' factor 
    | factor 
    ; 

factor : '(' expr ')' 
     | '-' factor 
     | NUMBER 
     | IDENTIFIER 
     ; 

이제 타이핑 규칙을 소개합시다. NUMBER 토큰을 FLT_NUMBER 및 INT_NUMBER로 구분합니다.우리 expr, term 및 factor 비 단말기뿐만 아니라 두 개로 분할 :

%token IDENTIFIER FLT_NUMBER INT_NUMBER 

stmt : IDENTIFIER '=' int_expr 
    | IDENTIFIER '=' flt_expr 
    ; 

int_expr : int_expr '+' int_term 
     | int_expr '-' int_term 
     | int_term 
     ; 

flt_expr : flt_expr '+' flt_term 
     | flt_expr '-' flt_term 
     | flt_term 
     ; 

int_term : int_term '*' int_factor 
     | int_term '/' int_factor 
     | int_factor 
     ; 

flt_term : flt_term '*' flt_factor 
     | flt_term '/' flt_factor 
     | flt_factor 
     ; 

int_factor : '(' int_expr ')' 
      | '-' int_factor 
      | INT_NUMBER 
      | int_identifier 
      ; 

flt_factor : '(' flt_expr ')' 
      | '-' flt_factor 
      | FLT_NUMBER 
      | flt_identifier 
      ; 

int_identifier : IDENTIFIER ; 

flt_identifier : IDENTIFIER ; 

우리의 문법이 시점에 서 같이, 충돌이있다 : 파서는 int_identifier 또는 식별자를 인식할지 여부를 말할 수 없다 a flt_identifier. 따라서 A = B을 IDENTIFIER = int_expr 또는 IDENTIFIER = flt_expr으로 줄이는 지 여부는 알 수 없습니다.

(여기는 Ruby에 대한 나의 이해가 조금 부드럽습니다. :) Ruby (대부분의 언어와 비슷 함)는 어휘 수준에서 의 방법을 제공하지 않으므로 식별자의 숫자 유형을 결정할 수 있습니다. 이것을 올드 스쿨 BASIC과 비교하십시오. 여기서 A는 숫자이고 A $는 문자열입니다. 즉, A #이 정수를 나타내고 A @가 부동를 나타내는 언어를 발명했다면이 작업을 할 수 있습니다.

int_term '*' flt_factor과 같이 제한된 혼합 유형 식을 허용하려면 문법이 훨씬 복잡해집니다.

이러한 문제를 해결할 수있는 방법이있을 수 있습니다. yacc/bison 이외의 기술로 만든 파서가 더 쉽게 만들 수 있습니다. 최소한 내 스케치는 당신에게 더 추구 할 수있는 아이디어를 줄 것입니다.