현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

코드의 자료구조가 이해되지 않습니다.

rlj1202의 이미지
글쓴이: rlj1202 / 작성시간: 일, 2019/06/09 - 7:32오후

https://swtch.com/~rsc/regexp/nfa.c.txt

위 주소의 코드를 보고 있었는데 이해가 되지 않는 부분이 두군데 있습니다. 일단 코드를 보면

/*
 * Since the out pointers in the list are always 
 * uninitialized, we use the pointers themselves
 * as storage for the Ptrlists.
 */
union Ptrlist
{
	Ptrlist *next;
	State *s;
};
 
/* Create singleton list containing just outp. */
Ptrlist*
list1(State **outp)
{
	Ptrlist *l;
 
	l = (Ptrlist*)outp;
	l->next = NULL;
	return l;
}

State의 정의 부분은 다음과 같습니다.

typedef struct State State;
struct State
{
	int c;
	State *out;
	State *out1;
	int lastlist;
};

일단, Ptrlist의 목적은 이름에서 알 수 있듯이 무언가의 리스트 이겠거니 싶었습니다. 그런데 Ptrlist는 union 타입이란 말이죠? 이해가 되지 않아서 그림을 그려봤는데 더 이해가 되지 않습니다.

음... union 타입이니까 Ptrlist의 맴버 변수 타입인 Ptrlist* 혹은 State* 둘 중 하나만 의미가 있겠다고 생각했습니다. 그렇게 생각하고 그림을 그려보았습니다. 만약 제가 그림을 제대로 그렸다면??? 저 자료구조는 전혀 리스트가 아닙니다. 그냥... 삼중 사중 포인터라는 느낌밖에 없습니다.

일단 그렇다 치고 list1() 함수도 이해할 수 없었습니다. 주석으로는 새로운 리스트를 만든다는데 함수에서 하는 일이라고는 그냥 type conversion 밖에 없습니다. 게다가 State** 를 Ptrlist* 로 캐스팅합니다. 이것도 이해가 안되서 그림을 그려봤는데 더 이해가 되지 않습니다.

일단 State** 값을 매개변수로 받았고 그 값을 Ptrlist* 변수에 넣었으니 결과는 위와 같을 것이라고 생각했습니다. 그렇다면 State* == Ptrlist 라는 것인가요???

kldp회원분들께 코드 해석을 ㅇ...요청드립니다.

Forums: 
프로그래밍 QnA
gkgkgk의 이미지

글쓴이: gkgkgk / 작성시간: 월, 2019/06/10 - 10:00오전

automata state machine 이론 같네요

rlj1202의 이미지

글쓴이: rlj1202 / 작성시간: 월, 2019/06/10 - 10:17오전

네, 오토마타를 공부하면서 찾은 코드입니다.

raymundo의 이미지

글쓴이: raymundo / 작성시간: 월, 2019/06/10 - 2:47오후

질문글 덕분에 신기한 코드 저도 배워가네요.

말로 설명하기는 힘든데, 예를 들어 "a|b" 라는 정규식을 NFA로 변환할 때

             +--------+   a
          +->+ state1 +--+
          |  +--------+  |
 +-----+  |              |   +-----+
>+Split+--+              +-->+Match|
 +-----+  |              |   +-----+
          |  +--------+  |
          +->+ state2 +--+
             +--------+   b

위와 같이 변환되겠죠.

그러면 state1 의 out 과 state2 의 out 필드가 동일하게 Match state 를 가리켜야 하는데, 두 out 필드를 보관하는 일과, 일괄적으로 Match를 가리키게 하는 과정을 저 Ptrlist 리스트를 써서 하고 있네요.

"a|b"를 일단 후위표기힌 "ab|"로 바꾼 다음에, a, b, |를 각각 읽은 시점에 스택에 들어가 있는 Frag구조체의 out 필드는 저 state1과 state2의 out 필드의 리스트입니다.

State*
post2nfa(char *postfix)
{
...
    for(p=postfix; *p; p++){
    ...
    }
/*
입력 데이터가 더 이상 없음
 
이 시점에 
stack 배열에는 하나의 Fragment가 있고, 그 Fragment의 start는 Split state를 가리키고 있고, out은 다음과 같이 리스트를 유지
 
stack[0].out --> state1의 out --> state2의 out --> NULL
 
이제 이 두 out 필드가 모두 Match state를 가리키도록 하는게 patch()의 일
*/
    patch(e.out, &matchstate);
 
/*
 patch 를 하고 나면
 
  state1의 out --> Match state
  state2의 out --> Match state
*/

좋은 하루 되세요!

rlj1202의 이미지

글쓴이: rlj1202 / 작성시간: 월, 2019/06/10 - 3:03오후

그림으로 그려보고나서 답변을 이해했네요. 그러니까, 말그대로 State* 주소값 리스트(Ptr list) 인데, union을 사용해서 일종의 State*와 Ptrlist*를 alias로 만들었다? 고 볼 수 있는 것 같네요. 정말... 공간 활용을 제대로 한 것 같아요.

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 화, 2019/06/11 - 2:33오전

덕분에 저도 좋은거 배워 갑니다.

댓글 달기

텍스트 포맷에 대한 자세한 정보

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.