LL(1) parser 만들 때 조언좀 부탁드립니다!

skyinyour의 이미지

안녕하세요 ~!

이번에 LL(1) parser 를 자바로 구현해보려고 하는데

보통 책이나 인터넷 example 을 통해서 보면 예를들어

(a+b)*2 이 문장 자체를 BNF grammer 를 토대로 문법체크를 하더라구요. 이에 대해서 파서 알고리즘을 (파서 테이블을 가지고 구현하는 방법) 이해해 보면 이해가 가는데

만약 제가 소스 코드를 읽어와서 파싱을 해보고 싶은데, 가령

test.ino 라는 파일을 읽어와서 문법체크를 해보고 싶습니다.

예를들면 int val = 3; 이어야 하는 문장이 ints val = 3; 이라던가 선언되지 않은 변수를 사용했다던가 세미콜론을 뺐다던가 등등 문법적인 오류를 체크하고 싶은데요.

먼저 머릿속에서 공회전이 도는게...

1. 파싱을 할려면 우선 스캐너를 사용해야 하는 것이지요? 스캐너가 토큰을 넘겨주면 파서는 토큰을 받아서 구문트리를 만는것이니까요 !

2. 스캐너를 통해서 토큰이 넘어오면, 파싱 테이블을 어떻게 만들어야 하는지 답이 나오질 않네요.. 대부분의 예들은 터미널과 논터미널을 정해놓고 grammer 에 대입하기 때문에 이해가 가지만
파일을 읽어서 스캐닝을 해야하니 스캐닝된 토큰들은 모두 터미널이잖아요. 예를들어 파일을 한줄씩 읽으면 int val=3; 여기서 5가지의 토큰들은 모두 터미널로 들어오기 때문에
파싱 테이블에서 column에 논터미널들이 위치해야 하는데 매번 한줄씩 읽을때 마다 column이 바뀔텐데 어떻게 그럼 파싱테이블을 만들 수 있는지 모르겠습니다 ㅠㅠ

3. BNF를 만들 때 가장 먼지 start 로 지정해줘야 하는 문법이 뭐가 되야하는지 고민입ㄴ다. 먼저 stmt 로 선언을 BNF 시작으로 해볼 까 하는데 어떤것을 먼저 해도 상관없을까요 ?
stmt -> 선언|iteration|IF|function call|assignmnet 로 생각해보았는데, 먼저 문장 자체가 변수 선언 혹은 함수 선언, 호출 등 선언, 그리고 대입연산 혹은 기타등등 산술연산, 반복문. 조건문등
문장자체를 기준으로 생각해보고 이렇게 나누어서 시작하여 digit 이나 identifier등 terminal로 연결해보려 합니다. 잘못된 생각일까요 ??

스캐너는 그럭저럭 구현했지만... 파서는 급이 다르네요 ㅠㅠ 혹시나 방향을 잘못 잡고 있다면 조언좀 부탁드립니다 ㅠ

jick의 이미지

LL(1) parser를 손으로 만든다면 가장 쉬운 방법은 아마 recursive descent parser일 것 같네요.

https://en.wikipedia.org/wiki/Recursive_descent_parser

문법의 규칙을 그대로 코드로 바꾸는 거니까 테이블을 만들 필요도 없습니다.

* 그나저나 일반적인 수식은 아마 LL(1) 파서로 파싱이 안 될 텐데요...

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.